Submission #1093052

#TimeUsernameProblemLanguageResultExecution timeMemory
1093052PagodePaivaCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
327 ms30396 KiB
#include<bits/stdc++.h> #define inf 1e16 #define int long long using namespace std; const int N = 100010; int dists[N], distt[N], dist[N][4]; vector <pair <int, int>> g[N]; int s, t, start, endd; int32_t main(){ int n, m; cin >> n >> m; cin >> s >> t; cin >> start >> endd; for(int i = 0;i < m;i++){ int a, b, w; cin >> a >> b >> w; g[a].push_back({b, w}); g[b].push_back({a, w}); } priority_queue <pair <int, int>> pq; for(int i = 1;i <= n;i++){ dists[i] = distt[i] = inf; dist[i][0] = dist[i][1] = dist[i][2] = dist[i][3] = inf; } dists[s] = 0; pq.push({0, s}); while(!pq.empty()){ auto [d, v] = pq.top(); pq.pop(); if(-d != dists[v]) continue; for(auto [x, w] : g[v]){ if(dists[x] > dists[v] + w){ dists[x] = dists[v] + w; pq.push({-dists[x], x}); } } } distt[t] = 0; pq.push({0, t}); while(!pq.empty()){ auto [d, v] = pq.top(); pq.pop(); if(-d != distt[v]) continue; for(auto [x, w] : g[v]){ if(distt[x] > distt[v] + w){ distt[x] = distt[v] + w; pq.push({-distt[x], x}); } } } dist[start][0] = 0; priority_queue <array <int, 3>> pqq; pqq.push({0, start, 0}); while(!pqq.empty()){ auto [d, v, flag] = pqq.top(); pqq.pop(); if(-d != dist[v][flag]) continue; if(flag == 0){ if(dist[v][flag+1] > dist[v][flag]){ dist[v][flag+1] = dist[v][flag]; pqq.push({-dist[v][flag+1], v, flag+1}); } if(dist[v][flag+2] > dist[v][flag]){ dist[v][flag+2] = dist[v][flag]; pqq.push({-dist[v][flag+2], v, flag+2}); } } if(flag == 1){ if(dist[v][flag+2] > dist[v][flag]){ dist[v][flag+2] = dist[v][flag]; pqq.push({-dist[v][flag+2], v, flag+2}); } } if(flag == 2){ if(dist[v][flag+1] > dist[v][flag]){ dist[v][flag+1] = dist[v][flag]; pqq.push({-dist[v][flag+1], v, flag+1}); } } for(auto [x, w] : g[v]){ if(flag == 0){ if(dist[x][0] > dist[v][0] + w){ dist[x][0] = dist[v][0] + w; pqq.push({-dist[x][0], x, 0}); } } else if(flag == 1){ if(dists[v] + distt[x] + w == dists[t]){ if(dist[x][1] > dist[v][1]){ dist[x][1] = dist[v][1]; pqq.push({-dist[x][1], x, 1}); } } } else if(flag == 2){ if(distt[v] + dists[x] + w == dists[t]){ if(dist[x][2] > dist[v][2]){ dist[x][2] = dist[v][2]; pqq.push({-dist[x][2], x, 2}); } } } else{ if(dist[x][3] > dist[v][3] + w){ dist[x][3] = dist[v][3] + w; pqq.push({-dist[x][3], x, 3}); } } } } cout << dist[endd][3] << '\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...