제출 #865461

#제출 시각아이디문제언어결과실행 시간메모리
865461AsamaiCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
274 ms20676 KiB
#include <bits/stdc++.h> using namespace std; template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;} template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;} #define all(a) a.begin(), a.end() #define pb push_back #define pf push_front #define fi first #define se second #define int long long typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; typedef pair<db, db> pdb; typedef pair<ld, ld> pld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> plli; typedef pair<int, ll> pill; const int MAX_N = 1e5 + 5; const ll inf = 1e18; int n, m, S, T, U, V; vector<pii> adj[MAX_N]; int distU[MAX_N], distV[MAX_N], distS[MAX_N], back[MAX_N]; int dp[MAX_N][2]; priority_queue<pii, vector<pii>, greater<pii>> pq; int ans = inf; void dijkstra1(int start, int *dist) { for (int i = 1; i <= n; i++) { dist[i] = inf; } dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().se; int currW = pq.top().fi; pq.pop(); for (auto it : adj[u]) { int v = it.fi; int w = it.se; if (currW + w < dist[v]) { dist[v] = currW + w; pq.push({dist[v], v}); } } } } void sol(int start, int end) { for (int i = 1; i <= n; i++) { dp[i][0] = dp[i][1] = distS[i] = inf; } distS[start] = 0; dp[start][0] = distU[start]; dp[start][1] = distV[start]; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().se; int currW = pq.top().fi; pq.pop(); if (currW > distS[u]) { continue; } for (auto it : adj[u]) { int v = it.fi; int w = it.se; if (currW + w > distS[v]) { continue; } if (currW + w == distS[v]) { minimize(dp[v][0], dp[u][0]); minimize(dp[v][1], dp[u][1]); } else { distS[v] = currW + w; pq.push({distS[v], v}); dp[v][0] = min(dp[u][0], distU[v]); dp[v][1] = min(dp[u][1], distV[v]); } } } dijkstra1(end, back); for (int i = 1; i <= n; i++) { bool ok = false; for (auto it : adj[i]) { int v = it.fi; int w = it.se; if (distS[i] + w + back[v] == distS[end]) { ok = true; break; } } if (ok) { minimize(ans, dp[i][0] + dp[i][1]); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> S >> T >> U >> V; for (int i = 1; i <= m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].pb({v, c}); adj[v].pb({u, c}); } dijkstra1(U, distU); dijkstra1(V, distV); sol(S, T); sol(T, S); cout << ans; return 0; } /* Tuesday, 24 October 2023 15:16:46 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...