제출 #758605

#제출 시각아이디문제언어결과실행 시간메모리
758605KN200711Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
377 ms26576 KiB
# include <bits/stdc++.h> # define fi first # define se second # define ll long long using namespace std; int N, M; int S, T, U, V; vector< pair<int, int> > edge[100001]; ll mn[4][100001]; bool vis[100001]; void djks(int id) { int st; if(id == 0) st = S; else if(id == 1) st = T; else if(id == 2) st = U; else st = V; for(int i=1;i<=N;i++) vis[i] = 0; priority_queue< pair<ll, int> > PQ; PQ.push(make_pair(0, st)); while(!PQ.empty()) { ll a = -PQ.top().fi; int b = PQ.top().se; PQ.pop(); if(vis[b]) continue; vis[b] = 1; mn[id][b] = a; for(auto p : edge[b]) { if(!vis[p.fi]) PQ.push(make_pair(-a-p.se, p.fi)); } } return; } vector<int> adj[100001]; // path from S to T in the most efficient ways ll pth[4][100001]; ll fn(int a, int id) { // cout<<a<<endl; if(pth[id][a] != 1e18) return pth[id][a]; pth[id][a] = mn[id][a]; for(auto p : adj[a]) { pth[id][a] = min(pth[id][a], fn(p, id)); } return pth[id][a]; } int main() { scanf("%d %d", &N, &M); scanf("%d %d %d %d", &S, &T, &U, &V); vector< pair< pair<int, int>, int> > jj; jj.clear(); for(int i=0;i<M;i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); jj.push_back(make_pair(make_pair(a, b), c)); edge[a].push_back(make_pair(b, c)); edge[b].push_back(make_pair(a, c)); } for(int i=0;i<4;i++) djks(i); ll cs = mn[0][T]; for(auto p : jj) { if(mn[0][p.fi.fi] + p.se + mn[1][p.fi.se] == cs) { adj[p.fi.fi].push_back(p.fi.se); } else if(mn[0][p.fi.se] + p.se + mn[1][p.fi.fi] == cs) { adj[p.fi.se].push_back(p.fi.fi); } } for(int i=1;i<=N;i++) pth[2][i] = pth[3][i] = 1e18; ll ans = mn[2][V]; for(int i=1;i<=N;i++) { // cout<<i<<" "<<mn[2][i]<<" "<<mn[3][i]<<endl; ans = min(ans, fn(i, 2) + mn[3][i]); ans = min(ans, fn(i, 3) + mn[2][i]); } printf("%lld\n", ans); }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d %d %d", &S, &T, &U, &V);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...