제출 #1038370

#제출 시각아이디문제언어결과실행 시간메모리
1038370kfhjadCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
166 ms24556 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<pair<int, int>> adj[100001]; void dijkstra(int X, auto& minCostX) { using E = pair<ll, int>; priority_queue<E, vector<E>, greater<E>> q; q.push({0, X}); while (!q.empty()) { auto [cost, node] = q.top(); q.pop(); if (cost != minCostX[node]) continue; for (auto [i, x] : adj[node]) { if (cost + x < minCostX[i]) q.push({minCostX[i] = cost + x, i}); } } } int main() { cin.tie(NULL) -> sync_with_stdio(false); int N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V; vector<ll> minCostS(N + 1, LLONG_MAX), minCostU(N + 1, LLONG_MAX), minCostV(N + 1, LLONG_MAX); minCostS[S] = minCostU[U] = minCostV[V] = 0; while (M--) { int a, b, x; cin >> a >> b >> x; adj[a].push_back({b, x}); adj[b].push_back({a, x}); } dijkstra(S, minCostS); dijkstra(U, minCostU); dijkstra(V, minCostV); vector<bool> visited(N + 1); queue<int> q; q.push(T); vector<vector<int>> DAG(N + 1), rDAG(N + 1); vector<int> indegree(N + 1), rIndegree(N + 1); while (!q.empty()) { int node = q.front(); q.pop(); for (auto [i, x] : adj[node]) if (minCostS[i] + x == minCostS[node]) { if (!visited[i]) q.push(i), visited[i] = true; DAG[i].push_back(node), rDAG[node].push_back(i); ++indegree[node], ++rIndegree[i]; } } vector<ll> RminU = minCostU; vector<ll> RminV = minCostV; q.push(T); while (!q.empty()) { int node = q.front(); q.pop(); for (auto i : rDAG[node]) { if (--rIndegree[i] == 0) q.push(i); RminU[i] = min(RminU[i], RminU[node]); RminV[i] = min(RminV[i], RminV[node]); } } ll ans = LLONG_MAX; q.push(S); while (!q.empty()) { int node = q.front(); q.pop(); ans = min(ans, minCostU[node] + RminV[node]); ans = min(ans, minCostV[node] + RminU[node]); for (auto i : DAG[node]) { if (--indegree[i] == 0) q.push(i); minCostU[i] = min(minCostU[i], minCostU[node]); minCostV[i] = min(minCostV[i], minCostV[node]); } } cout << min(minCostU[V], ans) << endl; return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

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

commuter_pass.cpp:8:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | void dijkstra(int X, auto& minCostX)
      |                      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...