Submission #783522

#TimeUsernameProblemLanguageResultExecution timeMemory
7835228pete8Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
217 ms25704 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second #define pb push_back #define p push #define pii pair<int,int> #define ppii pair<int,pii> #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #define set(x) memset(x,-1,sizeof(x)); int n,m,s,t,u,v; #define int long long const int mxn=1e5,inf=LONG_LONG_MAX/2; vector<pii>adj[mxn+10]; bitset<mxn+10>vis; void dijk(int st,vector<int>&dist){ priority_queue<pii,vector<pii>,greater<pii>>pq; pq.p({0,st}); dist[st]=0; while(!pq.empty()){ int cur=pq.top().s; pq.pop(); if(vis[cur])continue; vis[cur]=true; for(auto i:adj[cur]){ if(dist[i.f]>dist[cur]+i.s)dist[i.f]=dist[cur]+i.s,pq.p({dist[i.f],i.f}); } } vis.reset(); } int32_t main(){ fastio cin>>n>>m>>s>>t>>u>>v; while(m--){ int a,b,c;cin>>a>>b>>c; adj[a].pb({b,c}); adj[b].pb({a,c}); } vector<int>dist1(n+1,inf); vector<int>dist2(n+1,inf); dijk(u,dist1); dijk(v,dist2); priority_queue<ppii,vector<ppii>,greater<ppii>>pq; //dist cur pa pq.p({0,{s,0}}); vector<pair<int,pii>>dist(n+1,{inf,{inf,inf}}); dist[s].f=0; while(!pq.empty()){ int cur=pq.top().s.f,pa=pq.top().s.s,cd=pq.top().f; pq.pop(); if(vis[cur]){ if(cd==dist[cur].f){ int cnu=min(dist1[cur],dist[pa].s.f),cnv=min(dist2[cur],dist[pa].s.s); if(cnu+cnv<=dist[cur].s.f+dist[cur].s.s){ dist[cur].s.f=cnu; dist[cur].s.s=cnv; } } continue; } vis[cur]=true; dist[cur].s.f=min(dist1[cur],dist[pa].s.f); dist[cur].s.s=min(dist2[cur],dist[pa].s.s); for(auto i:adj[cur]){ if(dist[i.f].f==-1||dist[i.f].f>=dist[cur].f+i.s){ int ndu=min(dist[cur].s.f,dist1[i.f]),ndv=min(dist[cur].s.s,dist2[i.f]); dist[i.f]={dist[cur].f+i.s,{ndu,ndv}}; pq.p({dist[i.f].f,{i.f,cur}}); } } } cout<<min(dist[t].s.f+dist[t].s.s,dist1[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...