제출 #1043601

#제출 시각아이디문제언어결과실행 시간메모리
1043601VectorLiCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
358 ms19400 KiB
#include <bits/stdc++.h> #define long long long using namespace std; const int N = (int) 1E5; const long A = numeric_limits<long>::max(); int n, m; vector<pair<int, int>> e[N]; vector<long> Dijkstra(int i) { vector<long> d(n, A); set<pair<long, int>> s; d[i] = 0; s.insert({0, i}); while (not s.empty()) { int u = s.begin() -> second; s.erase(s.begin()); for (auto [v, w] : e[u]) { if (d[v] > d[u] + w) { s.erase({d[v], v}); d[v] = d[u] + w; s.insert({d[v], v}); } } } return d; } int s, t; int x, y; vector<long> d[4]; long c; void DP(int i) { vector<long> dd(n, A); vector<long> g(n); set<pair<long, int>> s; dd[i] = 0; g[i] = d[2][i]; s.insert({0, i}); // 如果一个节点在 s 到 t 的最短路上,我们就可以用来更新 // i 节点不是 s 就是 t,可以用来更新 // g 数组存储节点 x 到所有 i 之前的节点的最短路径,起始节点只有一个选项 c = min(c, g[i] + d[3][i]); while (not s.empty()) { int u = s.begin() -> second; s.erase(s.begin()); for (auto [v, w] : e[u]) { if (dd[v] > dd[u] + w) { s.erase({dd[v], v}); dd[v] = dd[u] + w; // 此时 v 还只有 u 一个可以到达的前驱,DP g[v] = min(d[2][v], g[u]); s.insert({dd[v], v}); } else if (dd[v] == dd[u] + w) { // 由于边权正,所有 v 的前驱都会枚举到 g[v] = min(g[v], g[u]); if (d[0][v] + d[1][v] == d[0][t]) { c = min(c, g[v] + d[3][v]); } } } } for (int u = 0; u < n; u++) { if (d[0][u] + d[1][u] == d[0][t]) { c = min(c, g[u] + d[3][u]); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; cin >> s >> t; cin >> x >> y; s = s - 1, t = t - 1; x = x - 1, y = y - 1; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u = u - 1, v = v - 1; e[u].push_back({v, w}); e[v].push_back({u, w}); } d[0] = Dijkstra(s); d[1] = Dijkstra(t); d[2] = Dijkstra(x); d[3] = Dijkstra(y); c = d[2][y]; DP(s); DP(t); cout << c << "\n"; 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...