Submission #923996

#	Time	Username	Problem	Language	Result	Execution time	Memory
923996		TAhmed33	Commuter Pass (JOI18_commuter_pass)	C++98	0 / 100	213 ms	27528 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int MAXN = 2e5 + 25;
vector <pair <ll, ll>> adj[MAXN];
ll dist[MAXN][2], dist2[MAXN], dist3[MAXN];
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater <>> pq;
	pq.push({0, s});
	for (int i = 1; i <= n; i++) {
		dist[i][0] = dist[i][1] = inf;
	}
	dist[s][0] = dist[t][1] = 0;
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist[k.second][0]) continue;
		for (auto j : adj[k.second]) {
			if (dist[j.first][0] > j.second + k.first) {
				dist[j.first][0] = j.second + k.first;
				pq.push({dist[j.first][0], j.first});
			}
		}
	}
	pq.push({0, t});
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist[k.second][1]) continue;
		for (auto j : adj[k.second]) {
			if (dist[j.first][1] > j.second + k.first) {
				dist[j.first][1] = j.second + k.first;
				pq.push({dist[j.first][1], j.first});
			}
		}
	}
	for (int i = 1; i <= n; i++) dist2[i] = dist3[i] = inf;
	dist2[u] = dist3[u] = 0;
	pq.push({0, u});
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist2[k.second]) continue;
		for (auto j : adj[k.second]) {
			ll cost = k.first;
			if (dist[k.second][0] + j.second == dist[j.first][0] && dist[j.first][1] + j.second == dist[k.second][1]) {

			} else {
				cost += j.second;
			}
			if (dist2[j.first] > cost) {
				dist2[j.first] = cost;
				pq.push({dist2[j.first], j.first});
			}
		}
	}
	pq.push({0, u});
	while (!pq.empty()) {
		auto k = pq.top();
		pq.pop();
		if (k.first > dist3[k.second]) continue;
		for (auto j : adj[k.second]) {
			ll cost = k.first;
			if (dist[k.second][1] + j.second == dist[j.first][1] && dist[j.first][0] + j.second == dist[k.second][0]) {

			} else {
				cost += j.second;
			}
			if (dist3[j.first] > cost) {
				dist3[j.first] = cost;
				pq.push({dist3[j.first], j.first});
			}
		}
	}
	cout << min(dist3[v], dist2[v]) << '\n';
}

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