Submission #1152070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152070		pinbu	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	465 ms	23556 KiB

commuter_pass

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

const int N = 100005;
const long long oo = 1e18;

int n, m, s1, t1, s2, t2;
vector<pair<int, long long>> adj[N];
long long ds[N], dt[N], dd[N][3];
void Dijkstra(int st, long long d[]) {
	for (int u = 1; u <= n; u++) d[u] = oo;
	d[st] = 0;
	priority_queue<pair<long long, int>> pq;
	pq.emplace(0, st);
	while (pq.size()) {
		int u; long long di; tie(di, u) = pq.top();
		di = -di;
		pq.pop();
		if (d[u] != di) continue;
		for (auto V: adj[u]) {
			int v; long long w; tie(v, w) = V;
			if (d[v] > di + w) {
				pq.emplace(-(d[v] = di + w), v);
			}
		}
	}
}
void Dijkstra21(void) {
	for (int u = 1; u <= n; u++) dd[u][0] = dd[u][1] = dd[u][2] = oo;
	dd[s2][0] = 0;
	priority_queue<pair<long long, pair<int, int>>> pq;
	pq.push({0, {s2, 0}});
	while (pq.size()) {
		int u = pq.top().second.first, b = pq.top().second.second; long long di = -pq.top().first;
		pq.pop();
		if (dd[u][b] != di) continue;
		if (b < 2) {
			if (dd[u][b + 1] > di) {
				pq.push({-(dd[u][b + 1] = di), {u, b + 1}});
			}
		}
		for (auto V: adj[u]) {
			int v; long long w; tie(v, w) = V;
			if (b != 1) {
				if (dd[v][b] > di + w) {
					pq.push({-(dd[v][b] = di + w), {v, b}});
				}
			} else {
				if (ds[u] + w + dt[v] == ds[t1] && dd[v][1] > di) {
					pq.push({-(dd[v][1] = di), {v, 1}});
				}
			}
		}
	}
}
void Dijkstra22(void) {
	for (int u = 1; u <= n; u++) dd[u][0] = dd[u][1] = dd[u][2] = oo;
	dd[s2][0] = 0;
	priority_queue<pair<long long, pair<int, int>>> pq;
	pq.push({0, {s2, 0}});
	while (pq.size()) {
		int u = pq.top().second.first, b = pq.top().second.second; long long di = -pq.top().first;
		pq.pop();
		if (dd[u][b] != di) continue;
		if (b < 2) {
			if (dd[u][b + 1] > di) {
				pq.push({-(dd[u][b + 1] = di), {u, b + 1}});
			}
		}
		for (auto V: adj[u]) {
			int v; long long w; tie(v, w) = V;
			if (b != 1) {
				if (dd[v][b] > di + w) {
					pq.push({-(dd[v][b] = di + w), {v, b}});
				}
			} else {
				if (ds[v] + w + dt[u] == ds[t1] && dd[v][1] > di) {
					pq.push({-(dd[v][1] = di), {v, 1}});
				}
			}
		}
	}
}
void solve(void) {
	cin >> n >> m >> s1 >> t1 >> s2 >> t2;
	for (int i = 1, a, b, w; i <= m; i++) {
		cin >> a >> b >> w;
		adj[a].emplace_back(b, w);
		adj[b].emplace_back(a, w);
	}
	Dijkstra(s1, ds); Dijkstra(t1, dt);
	long long ans = oo;
	Dijkstra21(); ans = min(ans, dd[t2][2]);
	Dijkstra22(); ans = min(ans, dd[t2][2]);
	cout << ans;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int TEST = 1;
    while (TEST--) solve();
    
    return 0;
}

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