Submission #1247999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247999		vlomaczk	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	535 ms	121248 KiB

commuter_pass

#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>;

ll M = 100'010;
vector<vector<vector<pair<pair<ll, ll>, ll>>>> g(4, vector<vector<pair<pair<ll, ll>, ll>>>(M));
vector<pair<pair<ll, ll>, ll>> edges;
ll inf = 3e15;

vector<vector<ll>> dijkstra(ll s) {
	vector<vector<ll>> dist(4, vector<ll>(M, inf));
	dist[0][s] = 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[msk][v]!=dv) continue;
		for(auto[sr, w] : g[msk][v]) {
			auto[u, msk2] = sr;
			if(dist[msk2][u] > dv + w) {
				dist[msk2][u] = dv + w;
				pq.push({-dv-w, {u, msk2}});
			}
		}
	}
	return dist;
}

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

	ll n, m;
	cin >> n >> m;
	ll s, t, u, v;
	cin >> s >> t >> u >> v;
	for(ll i=0; i<m; ++i) {
		ll a, b, c;
		cin >> a >> b >> c;
		edges.push_back({{a, b}, c});
		g[0][a].push_back({{b, 0}, c});
		g[0][b].push_back({{a, 0}, c});
	}
	vector<ll> distS = dijkstra(s)[0];
	vector<ll> distT = dijkstra(t)[0];
	ll ans = distS[t];
	for(auto[e, d] : edges) {
		auto[a, b] = e;
		if(distS[a] + d + distT[b] == ans) {
			g[0][a].push_back({{b, 1}, 0});
			g[1][a].push_back({{b, 1}, 0});
			
			g[0][b].push_back({{a, 2}, 0});
			g[2][b].push_back({{a, 2}, 0});
		} else if(distS[b] + d + distT[a] == ans) {
			g[0][b].push_back({{a, 1}, 0});
			g[1][b].push_back({{a, 1}, 0});

			g[0][a].push_back({{b, 2}, 0});
			g[2][a].push_back({{b, 2}, 0});
		}

		g[3][a].push_back({{b, 3}, d});
		g[3][b].push_back({{a, 3}, d});

		g[1][a].push_back({{b, 3}, d});
		g[1][b].push_back({{a, 3}, d});

		g[2][a].push_back({{b, 3}, d});
		g[2][b].push_back({{a, 3}, d});
		
	}
	for(ll msk=1; msk<3; ++msk) {
		for(ll i=1; i<=n; ++i) {
			g[msk][i].push_back({{i, 3}, 0});
		}
	}
	vector<vector<ll>> dist = dijkstra(u);
	ans = inf;
	for(ll i=0; i<4; ++i) ans = min(ans, dist[i][v]);
	cout << ans << "\n";

	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45