Submission #159910

#TimeUsernameProblemLanguageResultExecution timeMemory
159910XCoderCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
2064 ms21008 KiB
#include <bits/stdc++.h> #define FOR(i,s,e) for(int i=(s);i<(int)(e);i++) #define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++) #define REP(i,n) FOR(i,0,n) #define ALL(x) (x).begin(), (x).end() #define CLR(s) memset(s,0,sizeof(s)) #define PB push_back #define ITER(v) __typeof((v).begin()) #define FOREACH(i,v) for(ITER(v) i=(v).begin();i!=(v).end();i++) #define x first #define y second using namespace std; typedef long long LL; typedef pair<int,int> pii; typedef pair<LL, LL> pll; typedef map<int,int> mii; typedef vector<int> vi; const LL INF = 1LL << 60; using Graph = vector<vector<pii>>; using Dist = vector<LL>; using Node = tuple<LL, int>; // <cost, node_id> int N, M, S, T, U, V; Graph G; Dist compute_shortest_path(Graph &G, vector<int> src_nodes, int N) { Dist D(N + 1, INF); priority_queue<Node, vector<Node>, greater<Node>> pq; for (auto &src : src_nodes) { D[src] = 0LL; pq.push({D[src], src}); } while (!pq.empty()) { LL cur; int x; tie(cur, x) = pq.top(); pq.pop(); if (D[x] > cur) continue; for (auto &it : G[x]) { LL cost; int y; tie(y, cost) = it; if (cur + cost < D[y]) { D[y] = cur + cost; pq.push({D[y], y}); } } } return D; } Dist S_dist, T_dist, U_dist, V_dist; LL ST_shortest_path_cost; LL dfs(int x, LL u_min_dist, LL v_min_dist) { // x : current node // DFS - traverse all possible shortest paths LL ans = INF; // u -> some nodes visited -> x -> v u_min_dist = min(u_min_dist, U_dist[x]); ans = min(ans, u_min_dist + V_dist[x]); // v -> some nodes visited -> x -> u v_min_dist = min(v_min_dist, V_dist[x]); ans = min(ans, v_min_dist + U_dist[x]); for (auto &edge : G[x]) { int y, cost; tie(y, cost) = edge; if (S_dist[x] + cost + T_dist[y] == ST_shortest_path_cost) { // S -> x -> y -> T is a possible S-T shortest path //cout << x << "->" << y << endl; ans = min(ans, dfs(y, u_min_dist, v_min_dist)); } } return ans; } int main() { int A, B, C; cin >> N >> M >> S >> T >> U >> V; G.resize(N + 1); FOR(_, 0, M) { cin >> A >> B >> C; G[A].PB({B, C}); G[B].PB({A, C}); } S_dist = compute_shortest_path(G, {S}, N); T_dist = compute_shortest_path(G, {T}, N); U_dist = compute_shortest_path(G, {U}, N); V_dist = compute_shortest_path(G, {V}, N); //cout << src_dist[T] << " " << dst_dist[S] << endl; ST_shortest_path_cost = S_dist[T]; assert (S_dist[T] == T_dist[S]); // Case 1: Travel U -> some nodes along a shortest path -> V LL ans = dfs(S, INF, INF); //cout << ans << endl; // Case 2: Travel U -> V via direct shortest path Dist direct_dist = compute_shortest_path(G, {U}, N); ans = min(ans, direct_dist[V]); cout << ans << endl; 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...