제출 #869357

#제출 시각아이디문제언어결과실행 시간메모리
869357vjudge1Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
666 ms41872 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second #define ll long long int const int mxn=1e5+5; ll n,m,dis[mxn],s,t,u,v,ans=1e18; pair<int,int>par[mxn]; set<pair<ll,ll> >st,yal[mxn]; void dij(){ while(st.size()){ auto x=*st.begin(); st.erase({x.fr,x.sc}); for(auto i:yal[x.sc]){ if(dis[i.fr]>x.fr+i.sc){ st.erase({dis[i.fr],i.fr}); dis[i.fr]=x.fr+i.sc; st.insert({dis[i.fr],i.fr}); par[i.fr].fr=x.sc; par[i.fr].sc=i.sc; } } } } int main(){ cin>>n>>m; cin>>s>>t>>u>>v; for(int i=1;i<=m;i++){ int x,y,w; cin>>x>>y>>w; yal[x].insert({y,w}); yal[y].insert({x,w}); } for(int i=1;i<=n;i++){ dis[i]=(i==s)?0:1e18; st.insert({dis[i],i}); } dij(); for(int x=t;par[x].fr!=0;x=par[x].fr){ yal[x].erase({par[x].fr,par[x].sc}); yal[x].insert({par[x].fr,0}); yal[par[x].fr].erase({x,par[x].sc}); yal[par[x].fr].insert({x,0}); } for(int i=1;i<=n;i++){ dis[i]=(i==u)?0:1e18; st.insert({dis[i],i}); } dij(); cout<<dis[v]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...