제출 #391759

#제출 시각아이디문제언어결과실행 시간메모리
391759timmyfengCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
594 ms28372 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100001; vector<array<int, 2>> adj[N], dag[N]; int n; void dijkstra(int s, long long *dist) { priority_queue<array<long long, 2>> queue; fill(dist, dist + n + 1, LLONG_MAX); queue.push({0, s}); dist[s] = 0; while (!queue.empty()) { auto [d, u] = queue.top(); queue.pop(); d = -d; if (d > dist[u]) { continue; } for (auto [c, w] : adj[u]) { if (d + w < dist[c]) { dist[c] = d + w; queue.push({-dist[c], c}); } } } } long long dist[3][N]; long long solve(int s, int t) { priority_queue<array<long long, 3>> queue; for (int i = 0; i < 3; ++i) { fill(dist[i], dist[i] + n + 1, LLONG_MAX); } queue.push({0, s, 0}); dist[0][s] = 0; while (!queue.empty()) { auto [d, u, k] = queue.top(); queue.pop(); d = -d; if (d > dist[k][u]) { continue; } if (k < 2 && d < dist[k + 1][u]) { dist[k + 1][u] = d; queue.push(array<long long, 3>{-d, u, k + 1}); } for (auto [c, w] : (k == 1 ? dag[u] : adj[u])) { if (d + w < dist[k][c]) { dist[k][c] = d + w; queue.push(array<long long, 3>{-dist[k][c], c, k}); } } } return dist[2][t]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int m, s, t, x, y; cin >> n >> m >> s >> t >> x >> y; while (m--) { int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijkstra(s, dist[0]); dijkstra(t, dist[1]); for (int i = 1; i <= n; ++i) { for (auto [j, w] : adj[i]) { if (dist[0][i] + w + dist[1][j] == dist[0][t]) { dag[i].push_back({j, 0}); } } } cout << min(solve(x, y), solve(y, x)) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...