제출 #1022486

#제출 시각아이디문제언어결과실행 시간메모리
1022486sinatbtfardCommuter Pass (JOI18_commuter_pass)C++17
16 / 100
463 ms37992 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back using namespace std; const int maxn = 1e5 + 1; int n, m, S, T, U, V; ll dist[2][maxn], dist2[4][maxn]; vector <pair <int, ll>> adj[maxn]; set <pair <ll, int>> s; set <vector <ll>> s2; void dijkstra (int src, int x){ fill(dist[x], dist[x] + n + 1, 1e15); dist[x][src] = 0; s.insert({dist[x][src], src}); for (int i = 0; i < n; i++){ int v = (*s.begin()).second; s.erase(s.begin()); for (auto [u, w] : adj[v]){ if (dist[x][u] <= dist[x][v] + w) continue; s.erase({dist[x][u], u}); dist[x][u] = dist[x][v] + w; s.insert({dist[x][u], u}); } if (!s.size()) break; } } void dijkstra2 (){ for (int i = 0; i < 4; i++) fill(dist2[i], dist2[i] + n + 1, 1e15); dist2[0][U] = 0; s2.insert({0, U, 0, -1}); while (s2.size()){ vector <ll> x = (*s2.begin()); ll c = x[0], v = x[1], st = x[2], par = x[3]; s2.erase(s2.begin()); if (st == 0){ for (auto [u, w] : adj[v]){ // check whether we go through the shortest subpath in the opposing direction as s does or not if (dist[0][v] + dist[1][u] + w == dist[0][T]){ if (dist2[1][u] <= dist2[st][v]) continue; dist2[1][u] = dist2[st][v]; s2.insert({dist2[1][u], u, 1, v}); } if (dist[1][v] + dist[0][u] + w == dist[0][T]){ if (dist2[2][u] <= dist2[st][v]) continue; dist2[2][u] = dist2[st][v]; s2.insert({dist2[2][u], u, 2, v}); } } for (auto [u, w] : adj[v]){ // we choose not to enter through the shortest path node or the node is not a part of a shortest path if (dist2[0][u] <= dist2[st][v] + w) continue; dist2[0][u] = dist2[st][v] + w; s2.insert({dist2[0][u], u, 0, v}); } } if (st == 1){ // state where we go in the same flow as s to t (s -> t) for (auto [u, w] : adj[v]){ if (dist[0][v] + dist[1][u] + w == dist[0][T]){ if (dist2[1][u] <= dist2[st][v]) continue; dist2[1][u] = dist2[st][v]; s2.insert({dist2[1][u], u, 1, v}); } else{ if (dist2[3][u] <= dist2[st][v] + w) continue; dist2[3][u] = dist2[st][v] + w; s2.insert({dist2[3][u], u, 3, v}); } } } if (st == 2){ // state where we go in the opposing flow (t -> s) for (auto [u, w] : adj[v]){ if (dist[1][v] + dist[0][u] + w == dist[0][T]){ if (dist2[2][u] <= dist2[st][v]) continue; dist2[2][u] = dist2[st][v] + w; s2.insert({dist2[2][u], u, 2, v}); } else{ if (dist2[3][u] <= dist2[st][v] + w) continue; dist2[3][u] = dist2[st][v] + w; s2.insert({dist2[3][u], u, 3, v}); } } } if (st == 3){ // state where we have finished making use of s -> t for (auto [u, w] : adj[v]){ if (dist2[3][u] <= dist2[st][v] + w) continue; dist2[3][u] = dist2[st][v] + w; s2.insert({dist2[3][u], u, 3, v}); } } } } int main (){ ios_base::sync_with_stdio(0); cin >> n >> m >> S >> T >> U >> V; for (int x, y, z, i = 0; i < m; i++){ cin >> x >> y >> z; adj[x].pb({y, z}); adj[y].pb({x, z}); } dijkstra(S, 0); dijkstra(T, 1); dijkstra2(); cout << min({dist2[0][V], dist2[1][V], dist2[2][V], dist2[3][V]}); }

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

commuter_pass.cpp: In function 'void dijkstra2()':
commuter_pass.cpp:42:6: warning: unused variable 'c' [-Wunused-variable]
   42 |   ll c = x[0], v = x[1], st = x[2], par = x[3];
      |      ^
commuter_pass.cpp:42:37: warning: unused variable 'par' [-Wunused-variable]
   42 |   ll c = x[0], v = x[1], st = x[2], par = x[3];
      |                                     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...