Submission #1265276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265276		vlomaczk	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	13 ms	3512 KiB

ho_t4

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Edge {
	ll a, b, c, d;
};

ll n, m;
ll M = 210, inf = 1e17;
vector<vector<ll>> g(M), gt(M);
vector<Edge> e;

vector<vector<ll>> dijkstra(ll s) {
	vector<vector<ll>> dist(M, vector<ll>(2, inf));
	dist[s][0] = 0;
	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push({0, {s, 0}});
	while(pq.size()) {
		auto[dv, stat] = pq.top(); pq.pop();
		auto[v, msk] = stat; dv *= -1;
		if(dist[v][msk]!=dv) continue;
		for(auto i : g[v]) {
			if(dist[e[i].b][msk] > dist[v][msk] + e[i].c) {
				dist[e[i].b][msk] = dist[v][msk] + e[i].c;
				pq.push({-dist[e[i].b][msk], {e[i].b, msk}});
			}
		}
		if(msk) continue;
		for(auto i : gt[v]) {
			if(dv + e[i].c + e[i].d < dist[e[i].a][1]) {
				dist[e[i].a][1] = dv + e[i].c + e[i].d;
				pq.push({-dist[e[i].a][1], {e[i].a, 1}});
			}
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(ll i=0; i<m; ++i) {
		Edge x;
		cin >> x.a >> x.b >> x.c >> x.d;
		g[x.a].push_back(i);
		gt[x.b].push_back(i);
		e.emplace_back(x);
	}
	vector<vector<ll>> dist1 = dijkstra(1);
	vector<vector<ll>> distn = dijkstra(n);
	ll ans = dist1[n][0] + distn[1][0];
	ans = min(ans, dist1[n][1] + distn[1][0]);
	ans = min(ans, dist1[n][0] + distn[1][1]);
	if(ans >= inf) cout << "-1\n";
	else cout << ans << "\n";

	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63