제출 #75175

#제출 시각아이디문제언어결과실행 시간메모리
75175bogdan10bosCommuter Pass (JOI18_commuter_pass)C++14
55 / 100
417 ms49708 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO typedef long long LL; typedef pair<int, int> pii; typedef pair<LL, int> pli; int N, M, S, T, U, V; vector<int> pth; vector<pii> edg[100005]; priority_queue< pli, vector<pli>, greater<pli> > pq; class Dijkstra { public: int nod; vector<LL> d; void dijkstra(int _nod) { d.resize(N + 5); nod = _nod; for(int i = 1; i <= N; i++) d[i] = 1LL << 60; while(!pq.empty()) pq.pop(); d[nod] = 0; pq.push({0LL, nod}); while(!pq.empty()) { int nod = pq.top().second; LL val = pq.top().first; pq.pop(); if(d[nod] != val) continue; for(auto &e: edg[nod]) if(d[e.first] > val + e.second) { d[e.first] = val + e.second; pq.push({val + e.second, e.first}); } } } LL getd(int x) { return d[x]; } }dS, dT, dU, dV, djk[305]; int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &M); scanf("%d%d", &S, &T); scanf("%d%d", &U, &V); for(int i = 1; i <= M; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); edg[x].push_back({y, z}); edg[y].push_back({x, z}); } dS.dijkstra(S); dT.dijkstra(T); dU.dijkstra(U); dV.dijkstra(V); LL ans = dU.getd(V); LL dST = dS.getd(T); if(S == U) { for(int i = 1; i <= N; i++) if(dS.getd(i) + dT.getd(i) == dST) ans = min(ans, dV.getd(i)); printf("%lld\n", ans); exit(0); } if(N <= 300) { for(int i = 1; i <= N; i++) djk[i].dijkstra(i); for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if( (dS.getd(i) + djk[i].getd(j) + dT.getd(j) == dST) || (dS.getd(j) + djk[i].getd(j) + dT.getd(i) == dST) ) ans = min(ans, dU.getd(i) + dV.getd(j)); printf("%lld\n", ans); exit(0); } LL mnu = 1LL << 60, mnv = 1LL << 60; for(int i = 1; i <= N; i++) if(dS.getd(i) + dT.getd(i) == dST) { mnu = min(mnu, dU.getd(i)); mnv = min(mnv, dV.getd(i)); } ans = min(ans, mnu + mnv); printf("%lld\n", ans); return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &S, &T);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...