Submission #594056

#TimeUsernameProblemLanguageResultExecution timeMemory
594056rurutoria7Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
314 ms21996 KiB
#include <bits/stdc++.h> #define int long long #define rep(i,j,k) for (int i=j; i<=k; i++) #define de(x) cout << #x << "=" << x << ", " #define dd cout << '\n'; #define ff first #define ss second #define pb push_back #define lyx_my_wife ios::sync_with_stdio(0), cin.tie(0); using namespace std; typedef pair<int,int> pii; const int N = 1e5+10, M = 2e5+10; int n, m, s, t, u, v; vector<pii> G[N]; int disu[N], disv[N], diss[N], dist[N], vis[N]; int dpu[N], dpv[N], ans; void dijks(int rt, int dis[N], int fordp=0, int forans=0) { memset(dis, 0x3f, sizeof(disu)); memset(vis, 0, sizeof(vis)); priority_queue<pii, vector<pii>, greater<pii>> pq; dis[rt] = 0; pq.push({0, rt}); if (fordp) { memset(dpu, 0x3f, sizeof(dpu)); memset(dpv, 0x3f, sizeof(dpv)); } while(pq.size()) { int i = pq.top().ss, d = pq.top().ff; pq.pop(); if (vis[i]) continue; vis[i] = 1; if (fordp) { dpu[i] = min(dpu[i], disu[i]); dpv[i] = min(dpv[i], disv[i]); } for (auto e: G[i]) { int j = e.ss, w = e.ff; if (forans) { if (diss[j] != diss[i]-w) continue; ans = min(ans, dpu[j]+disv[i]); ans = min(ans, dpv[j]+disu[i]); } if (dis[j] > d+w) { dis[j] = d+w; pq.push({dis[j], j}); if (fordp) dpu[j] = dpu[i], dpv[j] = dpv[i]; } else if (dis[j] == d+w) { if (fordp) dpu[j] = min(dpu[j], dpu[i]), dpv[j] = min(dpv[j], dpv[i]); } } } } signed main() { lyx_my_wife cin >> n >> m >> s >> t >> u >> v; rep(_,1,m) { int i, j, w; cin >> i >> j >> w; G[i].pb({w,j}); G[j].pb({w,i}); } // dijks for disu, disv dijks(u,disu); dijks(v,disv); dijks(s,diss,1); ans = disu[v]; dijks(t,dist,0,1); cout << ans << '\n'; } /* 6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1 6 5 1 2 3 6 1 2 10 2 3 10 3 4 10 4 5 10 5 6 10 8 8 5 7 6 8 1 2 2 2 3 3 3 4 4 1 4 1 1 5 5 2 6 6 3 7 7 4 8 8 5 5 1 5 2 3 1 2 1 2 3 10 2 4 10 3 5 10 4 5 10 */ /* > 無向圖,選一條 s-t 最短路使其邊權歸零,使 u-v 路徑最短 將無向圖拆成有向圖,從 s 開始的最短路徑有一個 DAG as sDAG s->t最短路也有 DAG 屬於 sDAG as stDAG ! stDAG 的任何一條 st 路徑都是合法的最短路 ! stDAG inverse as tsDAG 的任何一條 ts 路徑都是合法的最短路 from u to v in stDAG from v to u in stDAG ! u -> (x -> y)stDAG -> v ! sv -> (x -> y)stDAG -> u ! ans = min(dis[u][x] + dis[y][v]) ! ans = min(dis[v][x] + dis[y][u]) ! ans = min(dis[u][x] + dis[v][y]) ! ans = min(dis[v][x] + dis[u][y]) + dpu: on stDAG, min dis[u][x] + dpv: on stDAG, min dis[v][x] + ans = min(ans, dpu + disv[i]) + ans = min(ans, dpv + disu[i]) */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...