제출 #754362

#제출 시각아이디문제언어결과실행 시간메모리
754362jamielimCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
518 ms19408 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; typedef vector<int> vi; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int n,m; int s,t,u,v; vector<ii> adj[100005]; ll dist[4][100005]; ll minsofar[2][100005]; priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq; void dijkstra(int idx,int source){ for(int i=0;i<n;i++)dist[idx][i]=LLINF; dist[idx][source]=0; pq.push(mp(0,source)); while(!pq.empty()){ pair<ll,int> cur=pq.top();pq.pop(); for(ii i:adj[cur.se]){ if(dist[idx][i.fi]>dist[idx][cur.se]+i.se){ dist[idx][i.fi]=dist[idx][cur.se]+i.se; pq.push(mp(dist[idx][i.fi],i.fi)); } } } } int main(){ scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--; int a,b,c; for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c);a--;b--; adj[a].pb(b,c); adj[b].pb(a,c); } dijkstra(0,u); dijkstra(1,v); dijkstra(2,s); ll ans=LLINF; for(int i=0;i<n;i++){ dist[3][i]=LLINF; minsofar[0][i]=dist[0][i]; minsofar[1][i]=dist[1][i]; } dist[3][t]=0; pq.push(mp(0,t)); while(!pq.empty()){ pair<ll,int> cur=pq.top();pq.pop(); for(ii i:adj[cur.se]){ if(dist[3][i.fi]>dist[3][cur.se]+i.se){ dist[3][i.fi]=dist[3][cur.se]+i.se; for(int j=0;j<2;j++)minsofar[j][i.fi]=min(minsofar[j][cur.se],dist[j][i.fi]); pq.push(mp(dist[3][i.fi],i.fi)); }else if(dist[3][i.fi]==dist[3][cur.se]+i.se){ for(int j=0;j<2;j++)minsofar[j][i.fi]=min(minsofar[j][cur.se],minsofar[j][i.fi]); } } } for(int i=0;i<n;i++){ if(dist[2][i]+dist[3][i]==dist[2][t]){ ans=min(ans,minsofar[0][i]+dist[1][i]); ans=min(ans,minsofar[1][i]+dist[0][i]); } } printf("%lld",min(ans,dist[0][v])); }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);s--;t--;u--;v--;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d%d",&a,&b,&c);a--;b--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...