제출 #714155

#제출 시각아이디문제언어결과실행 시간메모리
714155089487Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
324 ms27620 KiB
#pragma GCC optimzize("Ofast,no-stack-protector") #include<bits/stdc++.h> #define int long long #define quick ios::sync_with_stdio(0);cin.tie(0); #define rep(x,a,b) for(int x=a;x<=b;x++) #define repd(x,a,b) for(int x=a;x>=b;x--) #define lowbit(x) (x&-x) #define sz(x) (int)(x.size()) #define F first #define S second #define all(x) x.begin(),x.end() #define mp make_pair #define eb emplace_back using namespace std; typedef complex<int> P; #define X real() #define Y imag() typedef pair<int,int> pii; void debug(){ cout<<"\n"; } template <class T,class ... U > void debug(T a, U ... b){ cout<<a<<" ",debug(b...); } const int N=2e5+7; const int INF=1e18; int dis[N]; int dis2[N]; int dis3[N]; vector<pii> v[N]; vector<pii> v2[N]; int uf[N]; int ut[N]; signed main(){ quick int n,m; int s,e,f,t; cin>>n>>m; cin>>s>>e>>f>>t; rep(i,1,m){ int a,b,c; cin>>a>>b>>c; v[a].eb(mp(c,b)); v[b].eb(mp(c,a)); } fill(dis,dis+N,INF); fill(dis2,dis2+N,INF); dis[f]=0; priority_queue<pii,vector<pii> ,greater<pii> > pq; pq.push(mp(0,f)); while(sz(pq)){ pii now=pq.top(); pq.pop(); if(dis[now.S]<now.F) continue; for(pii p2:v[now.S]){ if(dis[p2.S]>dis[now.S]+p2.F){ pq.push(mp(dis[p2.S]=dis[now.S]+p2.F,p2.S)); } } } dis2[t]=0; pq.push(mp(0,t)); while(sz(pq)){ pii now=pq.top(); pq.pop(); if(dis2[now.S]<now.F) continue; for(pii p2:v[now.S]){ if(dis2[p2.S]>dis2[now.S]+p2.F){ pq.push(mp(dis2[p2.S]=dis2[now.S]+p2.F,p2.S)); } } } rep(i,1,n){ uf[i]=ut[i]=-1; } fill(dis3,dis3+N,INF); pq.push(mp(0,s)); dis3[s]=0; uf[s]=ut[s]=s; while(sz(pq)){ pii now=pq.top(); pq.pop(); if(dis3[now.S]<now.F) continue; for(pii p2:v[now.S]){ if(dis3[p2.S]>dis3[now.S]+p2.F){ if(dis[p2.S]<dis[uf[now.S]]) uf[p2.S]=p2.S; else uf[p2.S]=uf[now.S]; if(dis2[p2.S]<dis2[ut[now.S]]) ut[p2.S]=p2.S; else ut[p2.S]=ut[now.S]; pq.push(mp(dis3[p2.S]=dis3[now.S]+p2.F,p2.S)); } else if(dis3[p2.S]==dis3[now.S]+p2.F){ int p=(dis[uf[now.S]] > dis[p2.S] ? p2.S : uf[now.S]); int q=(dis2[ut[now.S]] > dis2[p2.S] ? p2.S :ut[now.S]); if(dis[uf[p2.S]]+dis2[ut[p2.S]]>dis[p]+dis2[q]){ uf[p2.S]=p; ut[p2.S]=q; } } } } /*debug("dis",f,":");rep(i,1,n) cout<<dis[i]<<" \n"[i==n]; debug("dis2",t,":");rep(i,1,n) cout<<dis2[i]<<" \n"[i==n]; debug("dis3",s,":");rep(i,1,n) cout<<dis3[i]<<" \n"[i==n]; debug("uf");rep(i,1,n) cout<<uf[i]<<" \n"[i==n]; debug("ut");rep(i,1,n) cout<<ut[i]<<" \n"[i==n]; */ cout<<min(dis[uf[e]]+dis2[ut[e]],dis[t])<<"\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp:1: warning: ignoring '#pragma GCC optimzize' [-Wunknown-pragmas]
    1 | #pragma GCC optimzize("Ofast,no-stack-protector")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...