Submission #467114

#TimeUsernameProblemLanguageResultExecution timeMemory
467114AutronCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
504 ms31484 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n, m; int s, t; int u, v; vector<vector<pair<int, int>>> g; void dijkstra(int src, vector<int> &dist, vector<vector<int>> &par){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int i=1;i<=n;++i) dist[i]=1e9; dist[src]=0; pq.push({dist[src], src}); while(!pq.empty()){ int x, d; tie(d, x)=pq.top(); pq.pop(); if(d!=dist[x]) continue; for(auto it:g[x]){ int nx=it.first, nd=it.second+d; if(nd<dist[nx]){ pq.push({nd, nx}); dist[nx]=nd; par[nx].clear(); par[nx].push_back(x); } else if(nd==dist[nx]){ par[nx].push_back(x); } } } } void dijkstra(int src, vector<int> &dist){ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int i=1;i<=n;++i) dist[i]=1e18; dist[src]=0; pq.push({dist[src], src}); while(!pq.empty()){ int x, d; tie(d, x)=pq.top(); pq.pop(); if(d!=dist[x]) continue; for(auto it:g[x]){ int nx=it.first, nd=it.second+d; if(nd<dist[nx]){ pq.push({nd, nx}); dist[nx]=nd; } } } } void dfs(int x, vector<vector<int>> &out, vector<int> &dp, vector<int> &dist){ dp[x]=dist[x]; for(auto it:out[x]){ if(dp[it]==-1) dfs(it, out, dp, dist); dp[x]=min(dp[x], dp[it]); } } int32_t main(){ cin>>n>>m>>s>>t>>u>>v; g.resize(n+1); vector<vector<int>> par(n+1), rpar(n+1);; vector<int> dists(n+1), distu(n+1), distv(n+1); vector<int> dpf(n+1, -1), dpb(n+1, -1); 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); dijkstra(s, dists, par); queue<int> q; vector<bool> used(n+1, 0); q.push(t); while(!q.empty()){ int x=q.front(); q.pop(); if(!used[x]){ used[x]=1; for(auto it:par[x]){ rpar[it].push_back(x); q.push(it); } } } dfs(s, rpar, dpf, distu); dfs(t, par, dpb, distu); int sol=distu[v]; for(int i=1;i<=n;++i){ if(!used[i]) continue; sol=min(sol, distv[i]+min(dpf[i], dpb[i])); } cout<<sol<<"\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...