제출 #1031663

#제출 시각아이디문제언어결과실행 시간메모리
1031663juicyCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
208 ms19436 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 1e5 + 5; int n, m; array<int, 2> a, b; long long F[2][N], G[2][N], dp[N][2]; vector<array<int, 2>> g[N]; void dijkstra(long long *d, int src) { fill(d + 1, d + n + 1, 1e18); d[src] = 0; using T = pair<long long, int>; priority_queue<T, vector<T>, greater<T>> pq; pq.push({0, src}); while (pq.size()) { auto [c, u] = pq.top(); pq.pop(); if (c != d[u]) { continue; } for (auto [v, c] : g[u]) { if (d[v] > d[u] + c) { pq.push({d[v] = d[u] + c, v}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < 2; ++i) { cin >> a[i]; } for (int i = 0; i < 2; ++i) { cin >> b[i]; } while (m--) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); g[v].push_back({u, c}); } for (int i = 0; i < 2; ++i) { dijkstra(F[i], a[i]); } for (int i = 0; i < 2; ++i) { dijkstra(G[i], b[i]); } vector<int> ord(n); iota(ord.begin(), ord.end(), 1); sort(ord.begin(), ord.end(), [&](int i, int j) { return F[0][i] < F[0][j]; }); auto check = [&](int u, int v, int c) { return F[0][v] + c + F[1][u] == F[0][a[1]]; }; long long res = 1e18; for (int u : ord) { for (int i = 0; i < 2; ++i) { dp[u][i] = G[i][u]; } for (auto [v, c] : g[u]) { if (check(u, v, c)) { for (int i = 0; i < 2; ++i) { dp[u][i] = min(dp[u][i], dp[v][i]); } } } for (int i = 0; i < 2; ++i) { res = min(res, dp[u][i] + G[i ^ 1][u]); } } cout << min(res, G[0][b[1]]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...