제출 #283416

#제출 시각아이디문제언어결과실행 시간메모리
283416YJUCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
590 ms34676 KiB
#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,no-stack-protector") using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; const ll MOD=1e9+7; const ll MOD2=998244353; const ll N=2e5+5; const ld pi=3.14159265359; const ll INF=(1LL<<60); #define SQ(i) ((i)*(i)) #define REP(i,n) for(ll i=0;i<n;i++) #define REP1(i,n) for(ll i=1;i<=n;i++) #define pb push_back #define mp make_pair #define X first #define Y second #define setp setprecision #define lwb lower_bound #define SZ(_a) (ll)_a.size() ll n,m,S,T,U,V,x,y,w,dis,ans; vector<pll> v[N]; vector<ll> nv[N]; ll dv[N],du[N],ds[N],uans[N],vans[N],tans[N]; ll dg[N]; priority_queue<pll,vector<pll>,greater<pll> > pq; queue<ll> Q; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m>>S>>T>>U>>V; REP(i,m){ cin>>x>>y>>w; v[x].pb(mp(y,w));v[y].pb(mp(x,w)); } //prepare REP1(i,n){ dv[i]=du[i]=ds[i]=uans[i]=vans[i]=tans[i]=INF; } // //build dis from U,V,S pq.push(mp(0,U)); while(SZ(pq)){ x=pq.top().Y;dis=pq.top().X; pq.pop(); if(dis>=du[x])continue; du[x]=dis; for(auto i:v[x])pq.push(mp(dis+i.Y,i.X)); } pq.push(mp(0,V)); while(SZ(pq)){ x=pq.top().Y;dis=pq.top().X; pq.pop(); if(dis>=dv[x])continue; dv[x]=dis; for(auto i:v[x])pq.push(mp(dis+i.Y,i.X)); } pq.push(mp(0,S)); while(SZ(pq)){ x=pq.top().Y;dis=pq.top().X; pq.pop(); if(dis>=ds[x])continue; ds[x]=dis; for(auto i:v[x])pq.push(mp(dis+i.Y,i.X)); } //end REP1(i,n){ for(auto j:v[i]){ if(ds[j.X]==ds[i]+j.Y){ nv[i].pb(j.X);++dg[j.X]; } } } Q.push(S); while(SZ(Q)){ x=Q.front(); Q.pop(); tans[x]=min(tans[x],min(uans[x]+dv[x],vans[x]+du[x])); for(auto i:nv[x]){ uans[i]=min(uans[i],min(uans[x],du[x])); vans[i]=min(vans[i],min(vans[x],dv[x])); tans[i]=min(tans[i],tans[x]); --dg[i]; if(dg[i]==0)Q.push(i); } } /*REP1(i,n){ cout<<i<<" "<<(uans[i]>=INF?-1:uans[i])<<" "<<(vans[i]>=INF?-1:vans[i])<<"\n"; }*/ ans=tans[T]; REP1(i,n)ans=min(ans,du[i]+dv[i]); cout<<ans<<"\n"; 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...