제출 #1090938

#제출 시각아이디문제언어결과실행 시간메모리
1090938chautanphatCommuter Pass (JOI18_commuter_pass)C++14
16 / 100
224 ms23244 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 1; int n, m, s, t, u, v; long long ans; vector<pair<int, int>> a[N]; vector<int> g[N]; vector<long long> ds, dt, du, dv, dp1(N, 1e16), dp2(N, 1e16); bool vs[N]; vector<long long> dijkstra(int s) { vector<long long> d(n+1, 1e16); priority_queue<pair<long long, int>> q; d[s] = 0; q.push({0, s}); while (!q.empty()) { long long dis = -q.top().first; int u = q.top().second; q.pop(); if (d[u] != dis) continue; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].first, w = a[u][i].second; if (d[u]+w < d[v]) { d[v] = d[u]+w; q.push({-d[v], v}); } } } return d; } pair<long long, long long> dfs(int u) { if (vs[u]) return {dp1[u], dp2[v]}; vs[u] = 1, dp1[u] = dv[u], dp2[u] = du[u]; for (int i = 0; i < (int)g[u].size(); i++) { int v = g[u][i]; pair<long long, long long> p = dfs(v); dp1[u] = min(dp1[u], p.first); dp2[u] = min(dp2[u], p.second); } ans = min(ans, min(du[u]+dp1[u], dv[u]+dp2[u])); return {dp1[u], dp2[u]}; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; while (m--) { int u, v, c; cin >> u >> v >> c; a[u].push_back({v, c}); a[v].push_back({u, c}); } ds = dijkstra(s); dt = dijkstra(t); du = dijkstra(u); dv = dijkstra(v); ans = du[v]; for (int u = 1; u <= n; u++) for (int i = 0; i < (int)a[u].size(); i++) if (ds[u]+a[u][i].second+dt[a[u][i].first] == ds[t]) g[u].push_back(a[u][i].first); for (int i = 1; i <= n; i++) if (!vs[i]) dfs(i); cout << ans; 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...