제출 #1083957

#제출 시각아이디문제언어결과실행 시간메모리
1083957NewtonabcCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
381 ms58824 KiB
#include<bits/stdc++.h> #define mp make_pair using namespace std; const int N=1e5+10; bool vs[4*N]; long long dista[N],distb[N],dist[4*N]; vector<pair<long long,int> > adj[4*N]; priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,m,s,t,st,ed; cin>>n >>m >>s >>t >>st >>ed; for(int i=0;i<m;i++){ int a,b; long long c; cin>>a >>b >>c; adj[a].push_back(mp(c,b)); adj[b].push_back(mp(c,a)); adj[3*n+a].push_back(mp(c,3*n+b)); adj[3*n+b].push_back(mp(c,3*n+a)); } for(int i=1;i<=n;i++) dista[i]=LLONG_MAX,distb[i]=LLONG_MAX; dista[s]=0,distb[t]=0; q.push(mp(0,s)); while(!q.empty()){ int u=q.top().second; q.pop(); if(vs[u]) continue; vs[u]=true; for(int i=0;i<adj[u].size();i++){ int v=adj[u][i].second; long long w=adj[u][i].first; if(dista[u]+w<dista[v]){ dista[v]=dista[u]+w; q.push(mp(dista[v],v)); } } } for(int i=1;i<=n;i++) vs[i]=false; q.push(mp(0,t)); while(!q.empty()){ int u=q.top().second; q.pop(); if(vs[u]) continue; vs[u]=true; for(int i=0;i<adj[u].size();i++){ int v=adj[u][i].second; long long w=adj[u][i].first; if(distb[u]+w<distb[v]){ distb[v]=distb[u]+w; q.push(mp(distb[v],v)); } } } /*for(int i=1;i<=n;i++) cout<<dista[i] <<" "; cout<<"\n"; for(int i=1;i<=n;i++) cout<<distb[i] <<" ";*/ for(int u=1;u<=n;u++){ adj[u].push_back(mp(0,n+u)); adj[u].push_back(mp(0,2*n+u)); adj[n+u].push_back(mp(0,3*n+u)); adj[2*n+u].push_back(mp(0,3*n+u)); for(int i=0;i<adj[u].size();i++){ int v=adj[u][i].second; long long w=adj[u][i].first; if(v>n) continue; if(dista[u]+w+distb[v]==dista[t]){ adj[n+u].push_back(mp(0,n+v)); adj[2*n+v].push_back(mp(0,2*n+u)); } } } for(int i=1;i<=4*n;i++) dist[i]=LLONG_MAX,vs[i]=false; dist[st]=0; q.push(mp(0,st)); while(!q.empty()){ int u=q.top().second; q.pop(); if(vs[u]) continue; vs[u]=true; for(int i=0;i<adj[u].size();i++){ int v=adj[u][i].second; long long w=adj[u][i].first; if(dist[u]+w<dist[v]){ dist[v]=dist[u]+w; q.push(mp(dist[v],v)); } } } cout<<dist[3*n+ed]; /*for(int i=1;i<=4*n;i++){ for(int j=0;j<adj[i].size();j++){ cout<<i <<" " <<adj[i][j].second <<" " <<adj[i][j].first <<"\n"; } }*/ }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
commuter_pass.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i=0;i<adj[u].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...