제출 #1153887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153887		h1euct	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	234 ms	21588 KiB

commuter_pass

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

#define fi first
#define se second

#define int long long

const int MX = 1e5 + 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<>> 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);
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> 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}});
	for (auto it : adj[u]) {
		int v = it.se;
		int uv = it.fi;
		if (Ls[u] + Lt[v] + uv == Ls[t]) {
			dp[u][1] = 0;
			q.push({dp[u][1], {u, 1}});
		}
	}
	while (!q.empty()) {
		int u = q.top().se.fi;
		int du = q.top().fi;
		int now = q.top().se.se;
		q.pop();
		if (du != dp[u][now]) continue;
		// if (u == 2 && now == 1) cout << du;
		for (auto it : adj[u]) {
			int v = it.se;
			int uv = it.fi;
			if (now == 0) {
				if (dp[v][0] > du + uv) {
					dp[v][0] = du + uv;
					q.push({dp[v][0], {v, 0}});
				}
				if (Ls[u] + uv + Lt[v] == Ls[t] && dp[v][1] > dp[u][0]) {
					dp[v][1] = dp[u][0];
					q.push({dp[v][1], {v, 1}});
				}
			}
			else if (now == 1) {
		// if (u == 1 && now == 1) cout << v << ' ' << Ls[u] <<' ' <<uv << ' ' << Lt[v] << ' ' << Ls[t] << '\n';
				if (Ls[u] + uv + Lt[v] == Ls[t] && dp[v][1] > dp[u][1]) {
					dp[v][1] = dp[u][1];
					q.push({dp[v][1], {v, 1}});
				}
				if (dp[v][2] > dp[u][1] + uv) {
					dp[v][2] = dp[u][1] + uv;
					q.push({dp[v][2], {v, 2}});
				}
			}
			else if (now == 2) {
				if (dp[v][2] > dp[u][2] + uv) {
					dp[v][2] = dp[u][2] + uv;
					q.push({dp[u][2], {u, 2}});
				}
			}
		}
	}
	// for (int i = 1; i <= n; i++) cerr << i <<' ' << dp[i][2] << '\n';
	int fn = min({dp[v][0], dp[v][1], dp[v][2]});
	
	// cout << dp[v][0] << ' ' << dp[v][1] << ' ' << dp[v][2] << ' ' << fn << '\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}});
	for (auto it : adj[u]) {
		int v = it.se;
		int uv = it.fi;
		if (Ls[u] + Lt[v] + uv == Ls[t]) {
			dp[u][1] = 0;
			q.push({dp[u][1], {u, 1}});
		}
	}
	while (!q.empty()) {
		int u = q.top().se.fi;
		int du = q.top().fi;
		int now = q.top().se.se;
		q.pop();
		if (du != dp[u][now]) continue;
		// if (u == 2 && now == 1) cout << du;
		for (auto it : adj[u]) {
			int v = it.se;
			int uv = it.fi;
			if (now == 0) {
				if (dp[v][0] > du + uv) {
					dp[v][0] = du + uv;
					q.push({dp[v][0], {v, 0}});
				}
				if (Ls[v] + uv + Lt[u] == Ls[t] && dp[v][1] > dp[u][0]) {
					dp[v][1] = dp[u][0];
					q.push({dp[v][1], {v, 1}});
				}
			}
			else if (now == 1) {
		// if (u == 1 && now == 1) cout << v << ' ' << Ls[u] <<' ' <<uv << ' ' << Lt[v] << ' ' << Ls[t] << '\n';
				if (Ls[v] + uv + Lt[u] == Ls[t] && dp[v][1] > dp[u][1]) {
					dp[v][1] = dp[u][1];
					q.push({dp[v][1], {v, 1}});
				}
				if (dp[v][2] > dp[u][1] + uv) {
					dp[v][2] = dp[u][1] + uv;
					q.push({dp[v][2], {v, 2}});
				}
			}
			else if (now == 2) {
				if (dp[v][2] > dp[u][2] + uv) {
					dp[v][2] = dp[u][2] + uv;
					q.push({dp[u][2], {u, 2}});
				}
			}
		}
	}
	fn = min({fn, dp[v][0], dp[v][1], dp[v][2]});
	cout << fn;
	return 0;
}
// binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong

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