제출 #705341

#제출 시각아이디문제언어결과실행 시간메모리
705341GrandTiger1729Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
299 ms27936 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; const long long INF = 1e18; int main(){ cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; int S, T, U, V; cin >> S >> T >> U >> V; S--, T--, U--, V--; vector<vector<pair<int, long long>>> g(n); for (int i = 0; i < m; i++){ int u, v, w; cin >> u >> v >> w; u--, v--; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } auto dijkstra = [&](int s){ priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.emplace(0, s); vector<long long> dis(n, INF); dis[s] = 0; vector<bool> vis(n); while (pq.size()){ auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = 1; for (auto &[v, w]: g[u]){ if (dis[v] > dis[u] + w){ dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } return dis; }; auto disU = dijkstra(U), disV = dijkstra(V); priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.emplace(0, S); vector<long long> dis(n, INF); dis[S] = 0; vector<bool> vis(n); vector<vector<int>> stk(n); vector<long long> ans(n, INF), minU(n, INF), minV(n, INF); while (pq.size()){ auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = 1; minU[u] = disU[u], minV[u] = disV[u]; for (auto &v: stk[u]){ ans[u] = min(ans[u], ans[v]); minU[u] = min(minU[u], minU[v]); minV[u] = min(minV[u], minV[v]); } ans[u] = min({ans[u], minU[u] + disV[u], minV[u] + disU[u]}); for (auto &[v, w]: g[u]){ if (dis[v] > dis[u] + w){ stk[v].clear(); stk[v].push_back(u); dis[v] = dis[u] + w; pq.emplace(dis[v], v); }else if (dis[v] == dis[u] + w){ stk[v].push_back(u); } } } cout << min(ans[T], disU[V]) << '\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...