제출 #866105

#제출 시각아이디문제언어결과실행 시간메모리
86610520163070Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
375 ms30052 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int inf=1e15,N=2e5+10; struct heap { int node; int len; bool operator < (const heap&x)const { return x.len<len; } }; priority_queue<heap> q; struct Edge { int to,next,len; }edge[N<<1]; int num,head[N],vis[N],n,m,s,t,u,v; int du[N],dv[N],ds[N],dt[N],f[N],g[N],ans; void add(int x,int y,int z) { edge[++num]=(Edge){y,head[x],z},head[x]=num; } void dijk(int st,int *dis) { for(int i=1;i<=n;i++) { vis[i]=0; dis[i]=inf; } dis[st]=0; q.push((heap){st,0}); while(q.size()) { int u=q.top().node; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[u]+edge[i].len) { dis[v]=dis[u]+edge[i].len; if(!vis[v]) q.push((heap){v,dis[v]}); } } } } void dfs(int u) { if(vis[u]) return; vis[u]=1; f[u]=dv[u],g[u]=du[u]; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(ds[u]+dt[v]+edge[i].len>ds[t]) continue; dfs(v); f[u]=min(f[u],f[v]); g[u]=min(g[u],g[v]); } ans=min(ans,min(f[u]+du[u],g[u]+dv[u])); } signed main() { cin>>n>>m; cin>>s>>t>>u>>v; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z),add(y,x,z); } dijk(s,ds); dijk(t,dt); dijk(u,du); dijk(v,dv); ans=du[v]; for(int i=1;i<=n;i++) vis[i]=0; dfs(s); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...