Submission #1086116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086116		ssitaram	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	247 ms	21544 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	--s; --t; --u; --v;
	vector<vector<pair<int, int>>> adj(n);
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		adj[--a].push_back({--b, c});
		adj[b].push_back({a, c});
	}
	vector<ll> toU(n, INT64_MAX), toV(n, INT64_MAX);
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, u});
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (toU[node] != INT64_MAX) continue;
			toU[node] = d;
			for (pair<int, int>& edge : adj[node]) {
				pq.push({d + edge.second, edge.first});
			}
		}
	}
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, v});
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (toV[node] != INT64_MAX) continue;
			toV[node] = d;
			for (pair<int, int>& edge : adj[node]) {
				pq.push({d + edge.second, edge.first});
			}
		}
	}
	ll ans = INT64_MAX;
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, s});
		vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX);
		vector<bool> vis(n);
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (vis[node]) continue;
			vis[node] = true;
			bestV[node] = min(bestV[node], toV[node]);
			best[node] = min(best[node], bestV[node] + toU[node]);
			if (node == t) {
				ans = min(ans, best[node]);
				break;
			}
			for (pair<int, int>& edge : adj[node]) {
				if (d + edge.second < toget[edge.first]) {
					toget[edge.first] = d + edge.second;
					bestV[edge.first] = bestV[node];
					best[edge.first] = best[node];
					pq.push({d + edge.second, edge.first});
				} else if (d + edge.second == toget[edge.first]) {
					bestV[edge.first] = min(bestV[edge.first], bestV[node]);
					best[edge.first] = min(best[edge.first], best[node]);
				}
			}
		}
	}
	{
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, t});
		vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX);
		vector<bool> vis(n);
		while (!pq.empty()) {
			ll d = pq.top().first;
			int node = pq.top().second;
			pq.pop();
			if (vis[node]) continue;
			vis[node] = true;
			bestV[node] = min(bestV[node], toV[node]);
			best[node] = min(best[node], bestV[node] + toU[node]);
			if (node == s) {
				ans = min(ans, best[node]);
				break;
			}
			for (pair<int, int>& edge : adj[node]) {
				if (d + edge.second < toget[edge.first]) {
					toget[edge.first] = d + edge.second;
					bestV[edge.first] = bestV[node];
					best[edge.first] = best[node];
					pq.push({d + edge.second, edge.first});
				} else if (d + edge.second == toget[edge.first]) {
					bestV[edge.first] = min(bestV[edge.first], bestV[node]);
					best[edge.first] = min(best[edge.first], best[node]);
				}
			}
		}
	}
	cout << min(ans, toV[u]) << '\n';
	return 0;
}

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