제출 #1087643

#제출 시각아이디문제언어결과실행 시간메모리
1087643FubuGoldCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
220 ms32540 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> using namespace std; const int maxn = 1e5 + 2; const int inf = LLONG_MAX / 4; int n,m,ans=inf; int D,S,T,U,V; vector<pii> a[maxn]; vector<int> b[maxn]; int d[5][maxn], tq[maxn], tu[maxn], tv[maxn], vst[maxn]; void dijkstra(int start, int cnt) { priority_queue<pii, vector<pii>, greater<pii> > qp; qp.push({0,start}); for (int i = 1; i <= n; i++) d[cnt][i] = inf; d[cnt][start] = 0; while (qp.size()) { int u,val; tie(val,u) = qp.top(); qp.pop(); if (d[cnt][u] < val) continue; for (pii tmp : a[u]) { int v,valv; tie(v,valv) = tmp; if (d[cnt][v] > valv + val) { d[cnt][v] = valv + val; qp.push({valv + val, v}); } } } } void dfs(int u) { tu[u] = d[2][u]; tv[u] = d[3][u]; ans = min(ans, tu[u] + tv[u]); vst[u] = 1; for (int v : b[u]) { if (vst[v] == 0) dfs(v); tu[u] = min(tu[u], tu[v]); tv[u] = min(tv[u], tv[v]); ans = min({ ans, d[2][u] + tv[v], d[3][u] + tu[v] }); } // cerr << u << " " << tu[u] << " " << tv[u] << endl; } signed main() { // freopen("BUS.INP", "r", stdin); // freopen("BUS.OUT", "w", stdout); cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; cin >> S >> T >> U >> V; for (int i= 1; i <= m; i++) { int x,y,h; cin >> x >> y >> h; a[x].push_back({y,h}); a[y].push_back({x,h}); } dijkstra(S,0); dijkstra(T,1); dijkstra(U,2); dijkstra(V,3); D = d[0][T]; // cerr << D << endl; for (int u = 1; u <= n; u++) { for (pii tmp : a[u]) { int v = tmp.first; if ( d[0][u] + tmp.second + d[1][v] == D ) { b[u].push_back(v); // cerr << u << " -> " << v << endl; } } } dfs(S); ans=min(ans,d[2][V]); 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...