Submission #1241992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241992		h1euct	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	279 ms	28656 KiB

commuter_pass

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

#define fi first
#define se second

#define int long long

const int MX = 2e5 + 5;
const int MOD = 1e9 + 7;

int n, m, s, t, u, v;
vector<pair<int, int>> adj[MX];

int Ls[MX], Lt[MX];

void dijkstra(int i1, int L[]) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for (int i = 1; i <= n; i++) L[i] = 1e18;
	L[i1] = 0;
	q.push({L[i1], i1});
	while (!q.empty()) {
		int u = q.top().se;
		int du = q.top().fi;
		q.pop();
		if (du != L[u]) continue;
		for (auto it : adj[u]) {
			int v = it.se;
			int uv = it.fi;
			if (du + uv < L[v]) {
				L[v] = du + uv;
				q.push({L[v], v});
			}
		}
	}
}

int dp[MX][3]; // 0 chua dung // 1 dang dung` // 2 da~ dung`

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// int test; cin>>test; while (test--) {}	
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 1; i <= m; i++) {
		int u1, v1, c1;
		cin >> u1 >> v1 >> c1;
		adj[u1].push_back({c1, v1});
		adj[v1].push_back({c1, u1});
	}
	dijkstra(s, Ls);
	dijkstra(t, Lt);
	// dp[u][0 1 2]
	// dang o dinh u 
	// 0: chua dung` duong chung
	// 1: dang tren duong chung
	// 2: da su dung xong duong chung
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = 1e18;
	}
	dp[u][0] = 0;
	q.push({dp[u][0], {u, 0}});
	while (!q.empty()) {
		int du = q.top().fi;
		int u = q.top().se.fi;
		int now = q.top().se.se;
		q.pop();
		if (du != dp[u][now]) continue;
		if (now == 0 && dp[u][1] > du) {
			dp[u][1] = du;
			q.push({dp[u][1], {u, 1}});
		}
		if (now == 1 && dp[u][2] > du) {
			dp[u][2] = du;
			q.push({dp[u][2], {u, 2}});
		}
		for (auto it : adj[u]) {
			int v = it.se;
			int uv = it.fi;
			// dp[v][0];
			if (now == 0 || now == 2) {
				if (dp[v][now] > du + uv) {
					dp[v][now] = du + uv;
					q.push({dp[v][now], {v, now}});
				}
			}
			else if (now == 1) {
				if (Ls[u] + uv + Lt[v] == Ls[t] && dp[v][1] > du) {
					dp[v][1] = du;
					q.push({dp[v][1], {v, 1}});
				}
			}
		}
	}
	int fn = min({dp[v][0], dp[v][1], dp[v][2]});
	// cout << dp[v][0] << ' ' << dp[v][1] << ' ' << dp[v][2] << '\n';
	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = 1e18;
	}
	dp[u][0] = 0;
	q.push({dp[u][0], {u, 0}});
	while (!q.empty()) {
		int du = q.top().fi;
		int u = q.top().se.fi;
		int now = q.top().se.se;
		q.pop();
		if (du != dp[u][now]) continue;
		if (now == 0 && dp[u][1] > du) {
			dp[u][1] = du;
			q.push({dp[u][1], {u, 1}});
		}
		if (now == 1 && dp[u][2] > du) {
			dp[u][2] = du;
			q.push({dp[u][2], {u, 2}});
		}
		for (auto it : adj[u]) {
			int v = it.se;
			int uv = it.fi;
			// dp[v][0];
			if (now == 0 || now == 2) {
				if (dp[v][now] > du + uv) {
					dp[v][now] = du + uv;
					q.push({dp[v][now], {v, now}});
				}
			}
			else if (now == 1) {
				if (Ls[v] + uv + Lt[u] == Ls[t] && dp[v][1] > du) {
					dp[v][1] = du;
					q.push({dp[v][1], {v, 1}});
				}
			}
		}
	}
	fn = min({fn, dp[v][0], dp[v][1], dp[v][2]});
	cout << fn;
	return 0;
}
// binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong

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