제출 #696489

#제출 시각아이디문제언어결과실행 시간메모리
696489therealpainCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
355 ms28900 KiB
#include <bits/stdc++.h> using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) a = b; else return false; return true; } const int N = 1e5 + 7; bool isIn[N]; int n, m, s, t, u, v; long long distS[N], distT[N], distU[N], distV[N], dpU[N], dpV[N]; vector <int> p[N][2]; vector <pair <int, int>> adj[N]; void dijkstra(int s, long long dist[]) { for (int i = 1; i < N; ++i) dist[i] = 1e18; priority_queue <pair <long long, int>> heap; dist[s] = 0; heap.emplace(0, s); while (heap.size()) { auto [da, a] = heap.top(); heap.pop(); da = -da; if (da != dist[a]) continue; for (auto [b, c] : adj[a]) { if (mini(dist[b], da + c)) heap.emplace(-dist[b], b); } } } void dfs1(int a) { dpU[a] = distV[a]; for (int b : p[a][0]) { if (dpU[b] < 0) dfs1(b); mini(dpU[a], dpU[b]); } } void dfs2(int b) { dpV[b] = distV[b]; for (int a : p[b][1]) { if (dpV[a] < 0) dfs2(a); mini(dpV[b], dpV[a]); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; ++i) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } dijkstra(s, distS); dijkstra(t, distT); dijkstra(u, distU); dijkstra(v, distV); for (int a = 1; a <= n; ++a) { for (auto [b, c] : adj[a]) if (distS[a] + distT[b] + c == distS[t]) { isIn[a] = isIn[b] = true; p[a][0].emplace_back(b); p[b][1].emplace_back(a); } } memset(dpU, -1, sizeof dpU); memset(dpV, -1, sizeof dpV); dfs1(s); dfs2(t); long long ans = distU[v]; for (int i = 1; i <= n; ++i) { if (isIn[i]) mini(ans, distU[i] + min(dpU[i], dpV[i])); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...