제출 #701625

#제출 시각아이디문제언어결과실행 시간메모리
701625EthanKim8683Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
999 ms262144 KiB
#include<bits/stdc++.h> using namespace std; using I=int; using Lli=long long int; using B=bool; const I N=100000; const Lli MAX=1e18; vector<pair<I,I>>adjs[N]; vector<I>incs[N]; Lli diss[N]; B viss[N]; priority_queue<pair<Lli,I>>ques; void add1(I a,Lli d,I p){ if(d>diss[a])return; if(d<diss[a])diss[a]=d,incs[a].clear(); if(d==diss[a])incs[a].push_back(p); ques.push({-d,a}); } void add2(I a,Lli d){ if(d>=diss[a])return; ques.push({-(diss[a]=d),a}); } void dfs(I a){ if(viss[a])return; viss[a]=1; for(auto b:incs[a]){ adjs[b].push_back({a,0}); dfs(b); } } I main(){ cin.tie(0)->sync_with_stdio(0); I n,m;cin>>n>>m; I s,t;cin>>s>>t,s--,t--; I u,v;cin>>u>>v,u--,v--; for(I i=0;i<m;i++){ I a,b,c;cin>>a>>b>>c,a--,b--; adjs[a].push_back({b,c}); adjs[b].push_back({a,c}); } fill_n(diss,n,MAX),add2(s,0); while(ques.size()){ auto[d,a]=ques.top();ques.pop(); if((d=-d)!=diss[a])continue; for(auto[b,c]:adjs[a])add1(b,d+c,a); } dfs(t); Lli res=MAX; fill_n(diss,n,MAX),add2(u,0); while(ques.size()){ auto[d,a]=ques.top();ques.pop(); if((d=-d)!=diss[a])continue; for(auto[b,c]:adjs[a])add2(b,d+c); } res=min(res,diss[v]); fill_n(diss,n,MAX),add2(v,0); while(ques.size()){ auto[d,a]=ques.top();ques.pop(); if((d=-d)!=diss[a])continue; for(auto[b,c]:adjs[a])add2(b,d+c); } res=min(res,diss[u]); printf("%lli\n",res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...