제출 #1193236

#제출 시각아이디문제언어결과실행 시간메모리
1193236vux2codeCommuter Pass (JOI18_commuter_pass)C++20
0 / 100
247 ms327680 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = numeric_limits<ll>::max() / 4; vector<ll> dijkstra(int src, const vector<vector<pair<int,ll>>> &adj) { int n = adj.size(); vector<ll> dist(n, INF); using pli = pair<ll,int>; priority_queue<pli, vector<pli>, greater<pli>> pq; dist[src] = 0; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; for (auto &[v, w] : adj[u]) { if (dist[v] > d + w) { dist[v] = d + w; pq.emplace(dist[v], v); } } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin >> N >> M; int S, T; cin >> S >> T; int U, V; cin >> U >> V; vector<vector<pair<int,ll>>> adj(N + 1); vector<tuple<int,int,ll>> edges; edges.reserve(M); for (int i = 0; i < M; ++i) { int a, b; ll c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); edges.emplace_back(a, b, c); } auto dS = dijkstra(S, adj); auto dT = dijkstra(T, adj); auto dU = dijkstra(U, adj); auto dV = dijkstra(V, adj); ll bestST = dS[T]; // Build shortest-path DAG vector<vector<int>> dag(N + 1); for (auto &[a, b, c] : edges) { if (dS[a] + c + dT[b] == bestST) dag[a].push_back(b); if (dS[b] + c + dT[a] == bestST) dag[b].push_back(a); } // Mark nodes on some SP from S to T vector<char> fromS(N + 1, 0), toT(N + 1, 0); { // BFS from S queue<int> q; q.push(S); fromS[S] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : dag[u]) if (!fromS[v]) { fromS[v] = 1; q.push(v); } } } { // reverse-DAG BFS from T vector<vector<int>> dag_rev(N + 1); for (int u = 1; u <= N; ++u) for (int v : dag[u]) dag_rev[v].push_back(u); queue<int> q; q.push(T); toT[T] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : dag_rev[u]) if (!toT[v]) { toT[v] = 1; q.push(v); } } } // DFS to enumerate SP nodes in DAG (pruned to nodes reaching T) vector<int> ord(N + 1, 0), rev; rev.reserve(N + 1); vector<int> parent; parent.reserve(N + 1); int K = 0; function<void(int)> dfs = [&](int u) { ord[u] = ++K; rev.push_back(u); for (int v : dag[u]) { if (fromS[v] && toT[v] && !ord[v]) { dfs(v); parent.push_back(ord[u]); } } }; dfs(S); // rev[i] is 0-indexed list of original nodes in DFS order; ord maps original to 1-based index // parent list is built in same order as rev except first element (S) has no parent vector<int> par(K+1); par[1] = 0; for (int i = 2; i <= K; ++i) par[i] = parent[i-2]; // Build reduced graph for dominator computation vector<vector<int>> g(K+1), rg(K+1); for (int idx = 0; idx < K; ++idx) { int u = rev[idx]; for (int v : dag[u]) { if (fromS[v] && toT[v]) { int iu = ord[u], iv = ord[v]; g[iu].push_back(iv); rg[iv].push_back(iu); } } } // Lengauer-Tarjan dominator tree vector<int> sdom(K+1), dom(K+1), dsu(K+1), label(K+1); vector<vector<int>> bucket(K+1); for (int i = 1; i <= K; ++i) { sdom[i] = label[i] = dsu[i] = i; dom[i] = 0; } function<int(int)> find = [&](int u) { if (dsu[u] == u) return u; int v = find(dsu[u]); if (sdom[label[dsu[u]]] < sdom[label[u]]) label[u] = label[dsu[u]]; return dsu[u] = v; }; auto unite = [&](int u, int v){ dsu[v] = u; }; for (int i = K; i >= 2; --i) { for (int j : rg[i]) { find(j); sdom[i] = min(sdom[i], sdom[label[j]]); } bucket[sdom[i]].push_back(i); unite(par[i], i); for (int j : bucket[par[i]]) { find(j); dom[j] = (sdom[label[j]] < sdom[j]) ? label[j] : par[i]; } bucket[par[i]].clear(); } for (int i = 2; i <= K; ++i) { if (dom[i] != sdom[i]) dom[i] = dom[dom[i]]; } dom[1] = 0; // Build dominator tree children vector<vector<int>> tree(K+1); for (int i = 2; i <= K; ++i) tree[dom[i]].push_back(i); // Compute Bmin over dominator subtree: Bmin_tree[i] = min dV over rev-subtree vector<ll> Bmin_tree(K+1, INF); for (int i = 1; i <= K; ++i) { int u = rev[i-1]; Bmin_tree[i] = dV[u]; } function<void(int)> dfs_bmin = [&](int u) { for (int v : tree[u]) { dfs_bmin(v); Bmin_tree[u] = min(Bmin_tree[u], Bmin_tree[v]); } }; dfs_bmin(1); // Compute answer ll answer = dU[V]; for (int i = 1; i <= K; ++i) { int u = rev[i-1]; if (dU[u] < INF && Bmin_tree[i] < INF) { answer = min(answer, dU[u] + Bmin_tree[i]); } } cout << answer << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...