제출 #998603

#제출 시각아이디문제언어결과실행 시간메모리
998603pannenkoekCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
187 ms24224 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = (a); i < (b); i++) #define pb push_back #define fi first #define se second using ll = long long; using ld = long double; using pii = pair<ll, ll>; const int MAXN = 1e5 + 5; const ll inf = 1e18 + 5; int n, m, s, t, u, v, perm[MAXN]; vector<pii> adj[MAXN]; set<pii> marked; bool vis1[MAXN], vis2[MAXN]; ll dis1[MAXN], dis2[MAXN], disu[MAXN], disv[MAXN], low1[MAXN], low2[MAXN]; ll dfs1(int i){ if(vis1[i]) return low1[i]; low1[i] = disv[i]; vis1[i] = 1; for(auto [j, d]: adj[i]){ if(dis1[i] + d + dis2[j] == dis1[t]) low1[i] = min(low1[i], dfs1(j)); } return low1[i]; } ll dfs2(int i){ if(vis2[i]) return low2[i]; low2[i] = disv[i]; vis2[i] = 1; for(auto [j, d]: adj[i]){ if(dis2[i] + d + dis1[j] == dis1[t]) low2[i] = min(low2[i], dfs2(j)); } return low2[i]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; rep(i, 0, m){ int a, b, c; cin >> a >> b >> c; a--; b--; adj[a].pb({b, c}); adj[b].pb({a, c}); } priority_queue<pii, vector<pii>, greater<pii>> pq; fill(dis1, dis1 + n, inf); dis1[s] = 0; pq.push({0, s}); while(!pq.empty()){ auto [d, cur] = pq.top(); pq.pop(); if(d > dis1[cur]) continue; for(auto [i, d2]: adj[cur]){ if(d + d2 < dis1[i]){ pq.push({d + d2, i}); dis1[i] = d + d2; } } } fill(dis2, dis2 + n, inf); dis2[t] = 0; pq.push({0, t}); while(!pq.empty()){ auto [d, cur] = pq.top(); pq.pop(); if(d > dis2[cur]) continue; for(auto [i, d2]: adj[cur]){ if(d + d2 < dis2[i]){ pq.push({d + d2, i}); dis2[i] = d + d2; } } } fill(disu, disu + n, inf); disu[u] = 0; pq.push({0, u}); while(!pq.empty()){ auto [d, cur] = pq.top(); pq.pop(); if(d > disu[cur]) continue; for(auto [i, d2]: adj[cur]){ if(d + d2 < disu[i]){ pq.push({d + d2, i}); disu[i] = d + d2; } } } fill(disv, disv + n, inf); disv[v] = 0; pq.push({0, v}); while(!pq.empty()){ auto [d, cur] = pq.top(); pq.pop(); if(d > disv[cur]) continue; for(auto [i, d2]: adj[cur]){ if(d + d2 < disv[i]){ pq.push({d + d2, i}); disv[i] = d + d2; } } } ll res = inf; rep(i, 0, n){ res = min(res, dfs1(i) + disu[i]); res = min(res, dfs2(i) + disu[i]); } cout << res << "\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...