제출 #75176

#제출 시각아이디문제언어결과실행 시간메모리
75176bogdan10bosCommuter Pass (JOI18_commuter_pass)C++14
16 / 100
520 ms15856 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; LL d[100005][3]; 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); for(int i = 1; i <= N; i++) d[i][0] = d[i][1] = d[i][2] = 1LL << 60; d[S][0] = 0; d[S][1] = dU.getd(S); d[S][2] = dV.getd(S); pq.push({0LL, S}); while(!pq.empty()) { int nod = pq.top().second; LL val = pq.top().first; pq.pop(); if(d[nod][0] != val) continue; d[nod][1] = min(d[S][1], dU.getd(nod)); d[nod][2] = min(d[S][2], dV.getd(nod)); if(val + dT.getd(nod) == dST) { ans = min(ans, d[nod][1] + dV.getd(nod)); ans = min(ans, d[nod][2] + dU.getd(nod)); } for(auto e: edg[nod]) { if(d[e.first][0] > val + e.second) { d[e.first][0] = val + e.second; d[e.first][1] = d[nod][1]; d[e.first][2] = d[nod][2]; pq.push({val + e.second, e.first}); } else if(d[e.first][0] == val + e.second) { d[e.first][1] = min(d[e.first][1], d[nod][1]); d[e.first][2] = min(d[e.first][2], d[nod][2]); } } } printf("%lld\n", ans); return 0; }

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

commuter_pass.cpp: In function 'int main()':
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", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
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", &S, &T);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:60: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:64: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...