제출 #632683

#제출 시각아이디문제언어결과실행 시간메모리
632683IwanttobreakfreeCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
428 ms29136 KiB
#include <iostream> #include <vector> #include <queue> using namespace std; #define int long long #define pii pair<int,int> int par(int a,vector<int>& id){ if(id[a]==a)return a; return id[a]=par(id[a],id); } void unite(int a,int b,vector<int>& id){ a=par(a,id),b=par(b,id); id[a]=b; } void nodijkstra(int a,int b,vector<vector<pii>>& p,vector<int>& dist,vector<int>& distu,vector<int>& distv,int s,int t){ queue<int> q; vector<vector<int>> g(p.size(),vector<int>()); q.push(a); vector<bool> seen(g.size(),false); while(!q.empty()){ int u=q.front(); seen[u]=true; q.pop(); for(auto v:p[u]){ if(dist[v.first]+v.second==dist[u]){ g[u].push_back(v.first); if(!seen[v.first])q.push(v.first); } } } int ans=distu[t],n=g.size(); vector<int> bestu(n),bestv(n),cnt(n),cnt2(n); for(int i=0;i<n;i++)for(auto v:g[i]){ cnt[v]++; cnt2[v]++; } for(int i=0;i<n;i++){ bestu[i]=distu[i]; bestv[i]=distv[i]; } q.push(a); while(!q.empty()){ int u=q.front(); //cout<<u<<' '; ans=min(ans,bestu[u]+distv[u]); q.pop(); for(auto v:g[u]){ cnt[v]--; bestu[v]=min(bestu[v],bestu[u]); if(!cnt[v])q.push(v); } } q.push(a); while(!q.empty()){ int u=q.front(); ans=min(ans,bestv[u]+distu[u]); q.pop(); for(auto v:g[u]){ cnt2[v]--; bestv[v]=min(bestv[v],bestv[u]); if(!cnt2[v])q.push(v); } } cout<<ans<<'\n'; } void dijkstra2(int s,int t,vector<vector<pii>>& g,int a,int b,vector<int>& dist){ priority_queue<pii> pqu,pqv; vector<int> distu(g.size(),1e18),distv(g.size(),1e18); pqu.push({0,s}); distu[s]=0; while(!pqu.empty()){ int u=pqu.top().second,d=-pqu.top().first; pqu.pop(); if(d>distu[u])continue; for(auto v:g[u]){ if(distu[v.first]>distu[u]+v.second){ distu[v.first]=distu[u]+v.second; pqu.push({-distu[v.first],v.first}); } } } pqv.push({0,t}); distv[t]=0; while(!pqv.empty()){ int u=pqv.top().second,d=-pqv.top().first; pqv.pop(); if(d>distv[u])continue; for(auto v:g[u]){ if(distv[v.first]>distv[u]+v.second){ distv[v.first]=distv[u]+v.second; pqv.push({-distv[v.first],v.first}); } } } int ans=1e18,n=g.size(); //vector<pii> distid(n,{1e18,1e18}); nodijkstra(b,a,g,dist,distu,distv,s,t); /*for(int i=0;i<n;i++){ cout<<id[i]<<' '; ans=min(ans,distid[i].first+distid[i].second); } cout<<ans<<'\n';*/ } void dijkstra(int a,int b,vector<vector<pii>>& g,int s,int t){ priority_queue<pii> pq; vector<int> dist(g.size(),1e18); pq.push({0,a}); dist[a]=0; while(!pq.empty()){ int u=pq.top().second,d=-pq.top().first; pq.pop(); if(d>dist[u])continue; for(auto v:g[u]){ if(dist[v.first]>dist[u]+v.second){ dist[v.first]=dist[u]+v.second; pq.push({-dist[v.first],v.first}); } } } //vector<int> id=nodijkstra(b,a,g,dist); //for(int i=0;i<g.size();i++)cout<<id[i]<<' '; dijkstra2(s,t,g,a,b,dist); } signed main(){ int n,m,u,v,s,t,x,y,w; cin>>n>>m>>s>>t>>u>>v; s--;t--;u--;v--; vector<vector<pii>> g(n,vector<pii>()); while(m--){ cin>>x>>y>>w; x--;y--; g[x].push_back({y,w}); g[y].push_back({x,w}); } dijkstra(s,t,g,u,v); }

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

commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, long long int, long long int, std::vector<long long int>&)':
commuter_pass.cpp:95:9: warning: unused variable 'ans' [-Wunused-variable]
   95 |     int ans=1e18,n=g.size();
      |         ^~~
commuter_pass.cpp:95:18: warning: unused variable 'n' [-Wunused-variable]
   95 |     int ans=1e18,n=g.size();
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...