제출 #1086116

#제출 시각아이디문제언어결과실행 시간메모리
1086116ssitaramCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
247 ms21544 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int s, t; cin >> s >> t; int u, v; cin >> u >> v; --s; --t; --u; --v; vector<vector<pair<int, int>>> adj(n); while (m--) { int a, b, c; cin >> a >> b >> c; adj[--a].push_back({--b, c}); adj[b].push_back({a, c}); } vector<ll> toU(n, INT64_MAX), toV(n, INT64_MAX); { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, u}); while (!pq.empty()) { ll d = pq.top().first; int node = pq.top().second; pq.pop(); if (toU[node] != INT64_MAX) continue; toU[node] = d; for (pair<int, int>& edge : adj[node]) { pq.push({d + edge.second, edge.first}); } } } { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, v}); while (!pq.empty()) { ll d = pq.top().first; int node = pq.top().second; pq.pop(); if (toV[node] != INT64_MAX) continue; toV[node] = d; for (pair<int, int>& edge : adj[node]) { pq.push({d + edge.second, edge.first}); } } } ll ans = INT64_MAX; { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, s}); vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX); vector<bool> vis(n); while (!pq.empty()) { ll d = pq.top().first; int node = pq.top().second; pq.pop(); if (vis[node]) continue; vis[node] = true; bestV[node] = min(bestV[node], toV[node]); best[node] = min(best[node], bestV[node] + toU[node]); if (node == t) { ans = min(ans, best[node]); break; } for (pair<int, int>& edge : adj[node]) { if (d + edge.second < toget[edge.first]) { toget[edge.first] = d + edge.second; bestV[edge.first] = bestV[node]; best[edge.first] = best[node]; pq.push({d + edge.second, edge.first}); } else if (d + edge.second == toget[edge.first]) { bestV[edge.first] = min(bestV[edge.first], bestV[node]); best[edge.first] = min(best[edge.first], best[node]); } } } } { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, t}); vector<ll> bestV(n, INT64_MAX), best(n, INT64_MAX), toget(n, INT64_MAX); vector<bool> vis(n); while (!pq.empty()) { ll d = pq.top().first; int node = pq.top().second; pq.pop(); if (vis[node]) continue; vis[node] = true; bestV[node] = min(bestV[node], toV[node]); best[node] = min(best[node], bestV[node] + toU[node]); if (node == s) { ans = min(ans, best[node]); break; } for (pair<int, int>& edge : adj[node]) { if (d + edge.second < toget[edge.first]) { toget[edge.first] = d + edge.second; bestV[edge.first] = bestV[node]; best[edge.first] = best[node]; pq.push({d + edge.second, edge.first}); } else if (d + edge.second == toget[edge.first]) { bestV[edge.first] = min(bestV[edge.first], bestV[node]); best[edge.first] = min(best[edge.first], best[node]); } } } } cout << min(ans, toV[u]) << '\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...