제출 #127305

#제출 시각아이디문제언어결과실행 시간메모리
127305HungAnhGoldIBO2020Commuter Pass (JOI18_commuter_pass)C++14
40 / 100
459 ms23276 KiB
#include<iostream> #include<vector> #include<queue> #define int long long using namespace std; const int N=1e5+2; const int inf=1e18+2; priority_queue<pair<int,int> > lis; vector<pair<int,int> > adj[N]; int dis[N],dis1[N],ans=inf,min1[N],dis2[N],min2[N],dis3[N]; void dijkstra(int x){ for(int i=0;i<adj[x].size();i++){ if(dis[adj[x][i].first]>dis[x]+adj[x][i].second){ dis[adj[x][i].first]=dis[x]+adj[x][i].second; lis.push({-dis[adj[x][i].first],adj[x][i].first}); } } } void dijkstra1(int x){ for(int i=0;i<adj[x].size();i++){ if(dis1[adj[x][i].first]>dis1[x]+adj[x][i].second){ dis1[adj[x][i].first]=dis1[x]+adj[x][i].second; lis.push({-dis1[adj[x][i].first],adj[x][i].first}); } } } void dijkstra3(int x){ for(int i=0;i<adj[x].size();i++){ if(dis3[adj[x][i].first]>dis3[x]+adj[x][i].second){ dis3[adj[x][i].first]=dis3[x]+adj[x][i].second; lis.push({-dis3[adj[x][i].first],adj[x][i].first}); } } } void dijkstra2(int x){ for(int i=0;i<adj[x].size();i++){ if(dis2[adj[x][i].first]>dis2[x]+adj[x][i].second){ dis2[adj[x][i].first]=dis2[x]+adj[x][i].second; min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]); min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]); lis.push({-dis2[adj[x][i].first],adj[x][i].first}); } else{ if(dis2[adj[x][i].first]==dis2[x]+adj[x][i].second){ min1[adj[x][i].first]=min(min1[adj[x][i].first],min1[x]); min2[adj[x][i].first]=min(min2[adj[x][i].first],min2[x]); } } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m,s,t,u,v,i,j,k,l; cin>>n>>m>>s>>t>>u>>v; for(i=1;i<=n;i++){ dis[i]=inf; dis1[i]=inf; dis3[i]=inf; dis2[i]=inf; } for(i=1;i<=m;i++){ cin>>j>>k>>l; adj[j].push_back({k,l}); adj[k].push_back({j,l}); } dis[u]=0; lis.push({0,u}); while(lis.size()){ if(-lis.top().first==dis[lis.top().second]){ dijkstra(lis.top().second); } lis.pop(); } dis1[v]=0; lis.push({0,v}); while(lis.size()){ if(-lis.top().first==dis1[lis.top().second]){ dijkstra1(lis.top().second); } lis.pop(); } dis3[t]=0; lis.push({0,t}); while(lis.size()){ if(-lis.top().first==dis3[lis.top().second]){ dijkstra3(lis.top().second); } lis.pop(); } dis2[s]=0; lis.push({0,s}); for(i=1;i<=n;i++){ min1[i]=dis[i]; min2[i]=dis1[i]; } ans=dis[v]; while(lis.size()){ if(-lis.top().first==dis2[lis.top().second]){ if(dis2[lis.top().second]+dis3[lis.top().second]==dis3[s]){ ans=min(ans,min1[lis.top().second]+dis1[lis.top().second]); ans=min(ans,min2[lis.top().second]+dis[lis.top().second]); } dijkstra2(lis.top().second); //cout<<lis.top().second<<" "<<ans<<endl; } lis.pop(); } cout<<ans; }

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

commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(long long int)':
commuter_pass.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra3(long long int)':
commuter_pass.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2(long long int)':
commuter_pass.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...