제출 #859004

#제출 시각아이디문제언어결과실행 시간메모리
859004PringCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
414 ms37944 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fs first #define sc second #define mp make_pair typedef pair<int, int> pii; typedef pair<int, pii> p3i; const int MXN = 100005, INF = 3000000000000000000; int n, m, s, t, u, v, ans; int dp[MXN], dp_v[MXN], dis[MXN], dis_v[MXN]; vector<pii> edge[MXN]; vector<int> DAG[MXN], DAG_INV[MXN]; inline void DIJKSTRA(int sr, int *dis, bool rec) { priority_queue<p3i, vector<p3i>, greater<p3i>> pq; fill(dis + 1, dis + n + 1, -1); pq.push(mp(0LL, mp(0LL, sr))); while (pq.size()) { p3i now = pq.top(); pq.pop(); int x = now.fs, p = now.sc.fs, id = now.sc.sc; if (rec) { if (dis[id] == x || dis[id] == -1) { DAG[id].push_back(p); } if (dis[id] != -1) continue; dis[id] = x; } else { if (dis[id] != -1) continue; dis[id] = x; } for (auto &e : edge[id]) { pq.push(mp(x + e.fs, mp(id, e.sc))); } } } void DFS(int id) { for (auto &i : DAG[id]) { if (DAG_INV[i].empty()) DFS(i); DAG_INV[id].push_back(i); } } inline void MAKE_DAG_INV() { DAG[s].pop_back(); // DFS(t); // for (int i = 1; i < n; i++) DAG[i].clear(); // for (int id = 1; id <= n; id++) { // for (auto &i : DAG_INV[id]) DAG[i].push_back(id); // } } void DFS2(int id) { dp[id] = dis[id]; dp_v[id] = dis_v[id]; for (auto &i : DAG[id]) { if (dp[i] == -1) DFS2(i); dp[id] = min(dp[id], dp[i]); dp_v[id] = min(dp_v[id], dp_v[i]); } ans = min(ans, dp[id] + dis_v[id]); ans = min(ans, dp_v[id] + dis[id]); } inline void DP() { fill(dp + 1, dp + n + 1, -1); fill(dp_v + 1, dp_v + n + 1, -1); dp[s] = dis[s]; dp_v[s] = dis_v[s]; ans = min(ans, dis[s] + dis_v[s]); DFS2(t); } int32_t main() { cin.tie(0) -> sync_with_stdio(false); int x, y, z; cin >> n >> m >> s >> t >> u >> v; while (m--) { cin >> x >> y >> z; edge[x].push_back(mp(z, y)); edge[y].push_back(mp(z, x)); } DIJKSTRA(s, dis, true); MAKE_DAG_INV(); DIJKSTRA(u, dis, false); DIJKSTRA(v, dis_v, false); ans = dis[v]; DP(); 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...