제출 #897185

#제출 시각아이디문제언어결과실행 시간메모리
897185aqxaCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
258 ms23732 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5; vector<pair<int, ll>> g[N]; vector<ll> ds, dt, du, dv; int n, m, s, t, u, v; vector<int> ord; void work(vector<ll> & d, int st) { d[st] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q; q.push({0, st}); while (!q.empty()) { int x = q.top().second; ll cd = q.top().first; q.pop(); if (d[x] < cd) continue; if (st == s) ord.push_back(x); for (pair<int, ll> next: g[x]) { ll nd = next.second + cd; int nx = next.first; if (nd < d[nx]) { d[nx] = nd; q.push({nd, nx}); } } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; ds = vector<ll>(n, 9e18); dt = vector<ll>(n, 9e18); du = vector<ll>(n, 9e18); dv = vector<ll>(n, 9e18); for (int i = 0; i < m; ++i) { int x, y; ll w; cin >> x >> y >> w; x--; y--; g[x].push_back({y, w}); g[y].push_back({x, w}); } work(ds, s); work(dt, t); work(du, u); work(dv, v); assert(ds[t] == dt[s]); assert(du[v] == dv[u]); vector<ll> dpu(n, 9e18), dpv(n, 9e18); vector<int> vis(n, 0); ll ans = du[v]; for (auto x: ord) { vis[x] = 1; if (ds[x] + dt[x] == ds[t]) { dpu[x] = du[x]; dpv[x] = dv[x]; for (auto last: g[x]) { int nd = last.first; if (vis[nd] && ds[nd] + dt[nd] == ds[t]) { dpu[x] = min(dpu[x], dpu[nd]); dpv[x] = min(dpv[x], dpv[nd]); } } ans = min(ans, dpu[x] + dv[x]); ans = min(ans, dpv[x] + du[x]); } } cout << ans << "\n"; 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...