제출 #1083217

#제출 시각아이디문제언어결과실행 시간메모리
1083217beanCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
234 ms20260 KiB
#include "bits/stdc++.h" using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; --s, --t; --u, --v; vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; i++) { int x, y, w; cin >> x >> y >> w; --x, --y; g[x].emplace_back(y, w); g[y].emplace_back(x, w); } const int64_t inf = 1e18; using P = pair<int64_t, int>; auto dijkstra = [&](int s) { const int64_t inf = int64_t(1e18); vector<int64_t> d(n, inf); priority_queue<P, vector<P>, greater<>> pq; pq.emplace(d[s] = 0, s); while (pq.size()) { int64_t d_v; int v; tie(d_v, v) = pq.top(); pq.pop(); if (d_v != d[v]) continue; for (auto &it : g[v]) { int u = it.first; int w = it.second; if (d[v] + w < d[u]) { pq.emplace(d[u] = d[v] + w, u); } } } return d; }; auto du = dijkstra(u); auto dv = dijkstra(v); auto dijkstra2 = [&](int s, int t) { vector<array<int64_t, 2>> dp(n, {inf, inf}); vector<int64_t> d(n, inf); priority_queue<P, vector<P>, greater<>> pq; dp[s][0] = du[s]; dp[s][1] = dv[s]; pq.emplace(d[s] = 0, s); while (pq.size()) { int64_t d_v; int v; tie(d_v, v) = pq.top(); pq.pop(); if (d_v != d[v]) continue; for (auto &it : g[v]) { int u, w; tie(u, w) = it; if (d[u] > d[v] + w) { dp[u][0] = min(dp[v][0], du[u]); dp[u][1] = min(dp[v][1], dv[u]); pq.emplace(d[u] = d[v] + w, u); } else if (d[u] == d[v] + w) { if (min(dp[v][0], du[u]) + min(dp[v][1], dv[u]) <= dp[u][0] + dp[u][1]) { dp[u][0] = min(dp[v][0], du[u]); dp[u][1] = min(dp[v][1], dv[u]); } } } } return dp[t][0] + dp[t][1]; }; int64_t res = du[v]; res = min(res, dijkstra2(s, t)); res = min(res, dijkstra2(t, s)); cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...