제출 #1086188

#제출 시각아이디문제언어결과실행 시간메모리
1086188f0rizenCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
202 ms25588 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9 + 7; const ll infll = 1e18; template<typename T> istream &operator>>(istream &is, vector<T> &a) { for (auto &i : a) { is >> i; } return is; } struct Edge { int to, w; }; vector<vector<Edge>> dag; vector<ll> da, db; vector<ll> dp_a, dp_b; vector<bool> used; ll ans = infll; void dfs(int v) { used[v] = 1; dp_a[v] = da[v]; dp_b[v] = db[v]; for (auto [u, w] : dag[v]) { if (!used[u]) { dfs(u); } dp_a[v] = min(dp_a[v], dp_a[u]); dp_b[v] = min(dp_b[v], dp_b[u]); } ans = min(ans, dp_a[v] + db[v]); ans = min(ans, dp_b[v] + da[v]); } int32_t main() { #ifdef LOCAL freopen("/tmp/input.txt", "r", stdin); #else ios::sync_with_stdio(false); cin.tie(nullptr); #endif int n, m; cin >> n >> m; int s, t, a, b; cin >> s >> t >> a >> b; --s, --t, --a, --b; vector<vector<Edge>> g(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; g[u].push_back({v, w}); g[v].push_back({u, w}); } auto dijkstra = [&](int s) { vector<ll> dp(n, infll); dp[s] = 0; using pii = pair<ll, int>; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({dp[s], s}); while (!pq.empty()) { auto [_, v] = pq.top(); pq.pop(); if (_ > dp[v]) { continue; } for (auto [u, w] : g[v]) { if (dp[u] > dp[v] + w) { dp[u] = dp[v] + w; pq.push({dp[u], u}); } } } return dp; }; vector<ll> ds = dijkstra(s); vector<ll> dt = dijkstra(t); dag.resize(n); for (int i = 0; i < n; ++i) { for (auto [j, w] : g[i]) { if (ds[i] + w + dt[j] == ds[t]) { dag[i].push_back({j, w}); } } } da = dijkstra(a); db = dijkstra(b); dp_a.resize(n); dp_b.resize(n); used.resize(n); ans = da[b]; dfs(s); 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...