제출 #922099

#제출 시각아이디문제언어결과실행 시간메모리
922099AiperiiiCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
472 ms28420 KiB
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=1e5+5; vector <pair <int,int> >g[N]; int ds[N],dv[N],du[N],vis[N],dpU[N],dpV[N]; int res=0; void dfs(int v){ if(vis[v])return; vis[v]=1; dpU[v]=du[v];dpV[v]=dv[v]; for(auto to : g[v]){ if(ds[v]==ds[to.ff]+to.ss){ dfs(to.ff); dpU[v]=min(dpU[v],dpU[to.ff]); dpV[v]=min(dpV[v],dpV[to.ff]); } } res=min(res,dpU[v]+dv[v]); res=min(res,dpV[v]+du[v]); } signed main(){ int n,m,s,t,u,w; cin>>n>>m>>s>>t>>u>>w; for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; g[a].pb({b,c}); g[b].pb({a,c}); } set <pair <int,int> > st; for(int i=1;i<=n;i++){ ds[i]=1e18;du[i]=1e18;dv[i]=1e18; } ds[s]=0; st.insert({0,s}); while(!st.empty()){ int v=st.begin()->second; st.erase(st.begin()); for(auto to : g[v]){ if(ds[to.ff]>ds[v]+to.ss){ st.erase({ds[to.ff],to.ff}); ds[to.ff]=ds[v]+to.ss; st.insert({ds[to.ff],to.ff}); } } } du[u]=0; st.insert({0,u}); while(!st.empty()){ int v=st.begin()->second; st.erase(st.begin()); for(auto to : g[v]){ if(du[to.ff]>du[v]+to.ss){ st.erase({du[to.ff],to.ff}); du[to.ff]=du[v]+to.ss; st.insert({du[to.ff],to.ff}); } } } dv[w]=0; st.insert({0,w}); while(!st.empty()){ int v=st.begin()->second; st.erase(st.begin()); for(auto to : g[v]){ if(dv[to.ff]>dv[v]+to.ss){ st.erase({dv[to.ff],to.ff}); dv[to.ff]=dv[v]+to.ss; st.insert({dv[to.ff],to.ff}); } } } res=du[w]; dfs(t); cout<<res<<"\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...