제출 #1278608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278608		IBory	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	168 ms	19360 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007;
vector<pii> G[MAX];
ll D[MAX], inQ[MAX], C[2][MAX];
pii dp[MAX];

void Dijkstra(int S, int N, ll* D) {
	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	PQ.emplace(D[S] = 0, S);
	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		if (cd > D[cur]) continue;
		for (auto& [next, nd] : G[cur]) {
			if (cd + nd >= D[next]) continue;
			PQ.emplace(D[next] = cd + nd, next);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, S, T, U, V;
	cin >> N >> M >> S >> T >> U >> V;
	for (int i = 1; i <= M; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		G[u].emplace_back(v, c);
		G[v].emplace_back(u, c);
	}

	memset(D, 0x3f, sizeof(D));
	Dijkstra(S, N, D);

	memset(C, 0x3f, sizeof(C));
	Dijkstra(U, N, C[0]);
	Dijkstra(V, N, C[1]);
	ll ans = C[0][V];
	
	fill(dp, dp + MAX, make_pair(1e18, 1e18));
	priority_queue<pii> PQ;
	PQ.emplace(D[T], T);
	while (!PQ.empty()) {
		auto [cd, cur] = PQ.top(); PQ.pop();
		ans = min(ans, C[0][cur] + dp[cur].second);
		ans = min(ans, C[1][cur] + dp[cur].first);
		dp[cur].first = min(dp[cur].first, C[0][cur]);
		dp[cur].second = min(dp[cur].second, C[1][cur]);
		for (auto& [next, d] : G[cur]) {
			if (D[next] + d != D[cur]) continue;
			if (!inQ[next]) {
				PQ.emplace(D[next], next);
				inQ[next] = 1;
			}
			dp[next].first = min(dp[next].first, dp[cur].first);
			dp[next].second = min(dp[next].second, dp[cur].second);
		}
	}

	cout << ans;
	return 0;
}

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