제출 #1093401

#제출 시각아이디문제언어결과실행 시간메모리
1093401KindaGoodGamesCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
2035 ms262144 KiB
#include<bits/stdc++.h> #define ll long long #define int ll #define pii pair<int,int> #define tiii tuple<int,int,int> #define tiiii tuple<int,int,int,int> using namespace std; ll INF = numeric_limits<ll>::max()/2; int32_t main(){ int n, m; cin >> n >> m; int s, t; cin >> s >> t; s--;t--; int ug, vg; cin >> ug >> vg; ug--;vg--; vector<vector<pii>> adj(n); for(int i = 0; i < m; i++){ int a,b,c; cin >> a >> b >> c; a--;b--; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } // Subcase 1 // Shortest paths from s to t vector<int> dist(n,INF); vector<set<int>> pre(n); priority_queue<tiii, vector<tiii>, greater<tiii>> pq; pq.push({0,s,s}); while(pq.size()){ int d, v, p; tie(d,v,p) = pq.top(); pq.pop(); if(dist[v] < d) continue; pre[v].insert(p); if(dist[v] == d) continue; dist[v] = d; for(auto pa : adj[v]){ pq.push({pa.second+d, pa.first, v}); } } // run Dijkstra again vector<int> dist2(n,INF); pq.push({0,ug,ug}); while(pq.size()){ int d, v, p; tie(d,v,p) = pq.top(); pq.pop(); if(dist2[v] <= d) continue; dist2[v] = d; for(auto pa : adj[v]){ pq.push({pa.second+d, pa.first, v}); } } // run Dijkstra again vector<int> distVG(n,INF); pq.push({0,vg,vg}); while(pq.size()){ int d, v, p; tie(d,v,p) = pq.top(); pq.pop(); if(distVG[v] <= d) continue; distVG[v] = d; for(auto pa : adj[v]){ pq.push({pa.second+d, pa.first, v}); } } // SP Graph vector<vector<int>> adjSP(n); vector<bool> vis(n); queue<int> qp; qp.push(t); while(qp.size()){ int i = qp.front(); qp.pop(); if(vis[i]) continue; vis[i] = true; for(auto u : pre[i]){ adjSP[i].push_back(u); //adjSP[u].push_back(i); if(!vis[u])qp.push(u); } } // remove add help vertices queue<tiiii> q; map<pii,int> used; int mi = INF; // cur | pre q.push({t,t, INF, INF}); while(q.size()) { int v, u, d, ds; tie(v,u,d,ds) = q.front(); q.pop(); //adj[v].push_back({u,0}); // distance to go from any node in path to the goal int newd = min(d, distVG[v]); // distance to go to any node in path from start int newds = min(ds, dist2[v]); mi = min(mi, newds + newd); used[{v,u}]++; for(auto w : adjSP[v]){ if(used[{w,v}] < n && w != v)q.push({w,v,newd,newds}); //if(!used.count({v,w}) && w != v)q.push({v,w,newd}); } } cout << min(mi,dist2[vg]) <<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...