제출 #682118

#제출 시각아이디문제언어결과실행 시간메모리
682118etheningCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
358 ms30396 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; ll INF = 1000'000'000'000'000'000ll; struct edge { int fr, to; ll we; }; struct pqnode { ll cDist; int node; }; void dijkstra(int n, const vector<vector<edge>>& E, int S, vector<ll>& dist) { auto cmp = [](const pqnode& u, const pqnode& v) { return u.cDist > v.cDist; }; priority_queue<pqnode, vector<pqnode>, decltype(cmp)> Q(cmp); dist = vector<ll>(n + 5, INF); dist[S] = 0; Q.push({.cDist = 0, .node = S}); while (!Q.empty()) { auto [cDist, node] = Q.top(); Q.pop(); if (cDist > dist[node]) continue; for (auto [fr, to, we] : E[node]) { if (dist[fr] + we < dist[to]) { dist[to] = dist[fr] + we; Q.push({.cDist = dist[to], .node = to}); } } } } void dagDp(int cur, const vector<vector<edge>>& G, const vector<ll>& uDist, const vector<ll>& vDist, vector<ll>& dist1, vector<ll>& dist2) { dist1[cur] = uDist[cur]; dist2[cur] = vDist[cur]; for (auto [fr, to, we]: G[cur]) { if (dist1[to] == -1) { dagDp(to, G, uDist, vDist, dist1, dist2); } dist1[cur] = min(dist1[cur], dist1[to]); dist2[cur] = min(dist2[cur], dist2[to]); } // cout << cur << " : "<< dist1[cur] << " " << dist2[cur] << endl; } int main() { int n, m; int s, t, u, v; cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> s >> t >> u >> v; vector<vector<edge>> E(n + 5, vector<edge>()); for (int i = 1; i <= m; i++) { int a, b; ll c; cin >> a >> b >> c; E[a].push_back({.fr = a, .to = b, .we = c}); E[b].push_back({.fr = b, .to = a, .we = c}); } vector<ll> sDist; dijkstra(n, E, s, sDist); vector<ll> tDist; dijkstra(n, E, t, tDist); vector<ll> uDist; dijkstra(n, E, u, uDist); vector<ll> vDist; dijkstra(n, E, v, vDist); // for (int i = 1; i <= n; i++) { // cout << "i: " << i << " s: " << sDist[i] << " t: " << tDist[i]; // cout << " u: " << uDist[i] << " v: " << vDist[i] << endl; // } vector<vector<edge>> G(n + 5, vector<edge>()); for (int i = 1; i <= n; i++) { for (auto [fr, to, we]: E[i]) { if (sDist[fr] + we + tDist[to] == sDist[t]) { G[fr].push_back({.fr = fr, .to = to, .we = 0}); } } } vector<ll> dist1(n + 5, -1); vector<ll> dist2(n + 5, -1); dagDp(s, G, uDist, vDist, dist1, dist2); ll ans = uDist[v]; for (int i = 1; i <= n; i++) { if (dist1[i] != -1) { ans = min(ans, min(dist1[i] + vDist[i], dist2[i] + uDist[i])); } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...