제출 #943112

#제출 시각아이디문제언어결과실행 시간메모리
943112noyancanturkCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
251 ms25588 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=1e5+500; #else const int lim=3e3+3; #endif #include "bits/stdc++.h" using namespace std; #define int int64_t #define pb push_back const int mod=998244353; //const int mod=(1ll<<61)-1; using pii=pair<int,int>; vector<pii>v[lim]; int n,m; inline void dj(int s,int*dist){ for(int i=1;i<=n;i++)dist[i]=LLONG_MAX; dist[s]=0; priority_queue<pii,vector<pii>,greater<pii>>pq; pq.push({0,s}); while(pq.size()){ auto [tm,now]=pq.top(); pq.pop(); if(tm^dist[now])continue; for(auto [j,c]:v[now]){ if(dist[now]+c<dist[j]){ dist[j]=dist[now]+c; pq.push({dist[j],j}); } } } } inline void solve(){ cin>>n>>m; int s,t; cin>>s>>t; int a,b; cin>>a>>b; for(int i=0;i<m;i++){ int x,y,c; cin>>x>>y>>c; v[x].pb({y,c}); v[y].pb({x,c}); } int dist[n+1],lead[n+1]; for(int i=0;i<=n;i++){ dist[i]=LLONG_MAX; lead[i]=0; } dist[s]=lead[s]=0; priority_queue<pii,vector<pii>,greater<pii>>pq; pq.push({0,s}); while(pq.size()){ auto [tm,now]=pq.top(); pq.pop(); if(tm^dist[now])continue; for(auto [j,c]:v[now]){ if(dist[now]+c<dist[j]){ dist[j]=dist[now]+c; pq.push({dist[j],j}); lead[j]=1; }else if(dist[now]+c==dist[j]){ lead[j]++; } } } int dista[n+1],distb[n+1],distT[n+1]; dj(a,dista); dj(b,distb); dj(t,distT); int ans=dista[b],dpa[n+1],dpb[n+1]; for(int i=0;i<=n;i++){ dpa[i]=dpb[i]=LLONG_MAX; } dpa[s]=distb[s]; dpb[s]=dista[s]; queue<int>q; q.push(s); while(q.size()){ int now=q.front(); q.pop(); dpa[now]=min(dpa[now],distb[now]); dpb[now]=min(dpb[now],dista[now]); ans=min(ans,dpa[now]+dista[now]); ans=min(ans,dpb[now]+distb[now]); for(auto [j,c]:v[now]){ if(dist[now]+c+distT[j]==dist[t]){ dpa[j]=min(dpa[j],dpa[now]); dpb[j]=min(dpb[j],dpb[now]); if(!(--lead[j])){ q.push(j); } } } } cout<<ans<<"\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #else #endif int t=1; //cin>>t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...