제출 #788730

#제출 시각아이디문제언어결과실행 시간메모리
788730tch1cherinCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
282 ms15292 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 5; vector<pair<int, int>> G[MAX_N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V; S--, T--, U--, V--; for (int i = 0; i < M; i++) { int A, B, C; cin >> A >> B >> C; A--, B--; G[A].push_back({B, C}); G[B].push_back({A, C}); } vector<int> order; vector<int64_t> dist(N); auto Dijkstra = [&](int start) { dist.assign(N, LLONG_MAX); order = vector<int>(); priority_queue<pair<int64_t, int>> q; q.push({dist[start] = 0, start}); while (!q.empty()) { auto [d, u] = q.top(); q.pop(); if (-d == dist[u]) { order.push_back(u); for (auto [v, w] : G[u]) if (dist[u] + w < dist[v]) q.push({-(dist[v] = w - d), v}); } } }; vector<int64_t> D[4]; Dijkstra(U), D[0] = dist; Dijkstra(V), D[1] = dist; Dijkstra(T), D[3] = dist; Dijkstra(S), D[2] = dist; reverse(order.begin(), order.end()); int64_t ans = LLONG_MAX; for (int u : order) { ans = min(ans, D[0][u] + D[1][u]); for (auto [v, w] : G[u]) { if (D[2][u] + w + D[3][v] == D[2][T]) { ans = min({ans, D[0][u] + D[1][v], D[0][v] + D[1][u]}); } } for (auto [v, w] : G[u]) { if (D[2][u] + w + D[3][v] == D[2][T]) { D[0][u] = min(D[0][u], D[0][v]); D[1][u] = min(D[1][u], D[1][v]); } } } cout << min(D[0][V], ans) << "\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...