제출 #1084206

#제출 시각아이디문제언어결과실행 시간메모리
1084206votranngocvyCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
260 ms24096 KiB
#include <bits/stdc++.h> using namespace std; #define NAME "task" #define int long long #define pii pair<int,int> #define fi first #define se second const int N = 1e5 + 5; const int inf = 0x3f3f3f3f3f3f3f3f; vector<pii>g[N]; vector<int>distU(N,inf),distV(N,inf); int dist[N],dpU[N],dpV[N],n,m; void dijkstra(int s,vector<int> &dist) { priority_queue<pii,vector<pii>,greater<pii>>q; q.push({0,s}); dist[s] = 0; while (!q.empty()) { int u = q.top().se,c = q.top().fi; q.pop(); if (dist[u] != c) continue; for (auto x: g[u]) { int v = x.fi,w = x.se; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push({dist[v],v}); } } } } int calc(int s,int t) { for (int i = 1; i <= n; i++) dist[i] = dpU[i] = dpV[i] = inf; priority_queue<pii,vector<pii>,greater<pii>>q; dist[s] = 0,dpU[s] = distU[s],dpV[s] = distV[s]; q.push({0,s}); while (!q.empty()) { int u = q.top().se,c = q.top().fi; q.pop(); if (dist[u] != c) continue; for (auto x: g[u]) { int v = x.fi,w = x.se; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; dpU[v] = min(distU[v],dpU[u]); dpV[v] = min(distV[v],dpV[u]); q.push({dist[v],v}); } else if (dist[v] == dist[u] + w && min(distU[v],dpU[u]) + min(distV[v],dpV[u]) <= dpU[v] + dpV[v]) { dpU[v] = min(distU[v],dpU[u]); dpV[v] = min(distV[v],dpV[u]); } } } return dpU[t] + dpV[t]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int s,t,u,v; cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { int a,b,c; cin >> a >> b >> c; g[a].push_back({b,c}); g[b].push_back({a,c}); } dijkstra(u,distU); dijkstra(v,distV); cout << min({distU[v],calc(s,t),calc(t,s)}) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...