제출 #911440

#제출 시각아이디문제언어결과실행 시간메모리
911440GhettoCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
379 ms28596 KiB
/* Disconnected? */ #include <bits/stdc++.h> using namespace std; using lint = long long; using pil = pair<int, lint>; using pli = pair<lint, int>; const int MAX_N = 1e5 + 5; const lint INF = 1e15; int n, m; int s, t; int u, v; vector<pil> adj[MAX_N]; bool seen[MAX_N]; lint min_dist[MAX_N]; void init() { for (int i = 1; i <= n; i++) { seen[i] = false; min_dist[i] = INF; } } priority_queue<pli, vector<pli>, greater<pli>> order; vector<int> backtrack_adj[MAX_N]; void dijk(int start, bool do_backtrack) { init(); min_dist[start] = 0; order.push({0, start}); while (order.size()) { int y = order.top().second; order.pop(); if (seen[y]) continue; seen[y] = true; for (pil e : adj[y]) { int z = e.first; lint len = e.second; lint new_dist = min_dist[y] + len; if (new_dist < min_dist[z]) { if (do_backtrack) backtrack_adj[z] = {y}; min_dist[z] = new_dist; order.push({new_dist, z}); } else if (new_dist == min_dist[z] && do_backtrack) backtrack_adj[z].push_back(y); } } } bool seen2[MAX_N]; void dfs(int y) { seen2[y] = true; for (int z : backtrack_adj[y]) { if (seen2[z]) continue; dfs(z); } } lint u_dist[MAX_N], v_dist[MAX_N]; lint v_dp[MAX_N]; bool v_seen[MAX_N]; lint find_v_dp(int y) { if (v_seen[y]) return v_dp[y]; v_dp[y] = v_dist[y]; for (int z : backtrack_adj[y]) { assert(seen2[z]); v_dp[y] = min(v_dp[y], find_v_dp(z)); } v_seen[y] = true; return v_dp[y]; } lint u_dp[MAX_N]; bool u_seen[MAX_N]; lint find_u_dp(int y) { if (u_seen[y]) return u_dp[y]; u_dp[y] = u_dist[y]; for (int z : backtrack_adj[y]) { assert(seen2[z]); u_dp[y] = min(u_dp[y], find_u_dp(z)); } u_seen[y] = true; return u_dp[y]; } int main() { // freopen("commuter.in", "r", stdin); cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { int y, z; lint len; cin >> y >> z >> len; adj[y].push_back({z, len}); adj[z].push_back({y, len}); } dijk(s, true); dfs(t); for (int i = 1; i <= n; i++) if (!seen2[i]) backtrack_adj[i].clear(); // cout << min_dist[t] << endl; // for (int i = 1; i <= n; i++) { // cout << i << ": "; // for (int in : backtrack_adj[i]) // cout << in << " "; // cout << endl; // } dijk(u, false); for (int i = 1; i <= n; i++) u_dist[i] = min_dist[i]; dijk(v, false); for (int i = 1; i <= n; i++) v_dist[i] = min_dist[i]; // for (int i = 1; i <= n; i++) { // cout << i << ": " << u_dist[i] << " " << v_dist[i] << endl; // } lint ans = u_dist[v]; for (int w = 1; w <= n; w++) { if (!seen2[w]) continue; ans = min(ans, u_dist[w] + find_v_dp(w)); } for (int w = 1; w <= n; w++) { if (!seen2[w]) continue; ans = min(ans, v_dist[w] + find_u_dp(w)); } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...