제출 #654094

#제출 시각아이디문제언어결과실행 시간메모리
654094tvladm2009Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
338 ms29136 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int N = (int) 1e5 + 7; const int INF = (ll) 1e18; int cnt[N]; vector<int> adj[N]; ll dist[N], minU[N], minV[N]; bool vis[N]; int n, m, s, t, u, v; struct Edge { int to; int cost; }; vector<Edge> g[N]; void dijkstra(int start, vector<ll> &dist) { for (int i = 1; i <= n; i++) { dist[i] = INF; vis[i] = 0; } priority_queue<pair<int, int>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u] == 1) { continue; } vis[u] = 1; for (auto &edg : g[u]) { int v = edg.to, relax = edg.cost; if (dist[u] + relax < dist[v]) { dist[v] = dist[u] + relax; pq.push({-dist[v], v}); } } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; g[x].push_back({y, z}); g[y].push_back({x, z}); } vector<ll> distS(n + 1), distT(n + 1), distU(n + 1), distV(n + 1); dijkstra(s, distS); dijkstra(t, distT); dijkstra(u, distU); dijkstra(v, distV); for (int u = 1; u <= n; u++) { for (auto &edg : g[u]) { if (distS[u] + edg.cost + distT[edg.to] == distS[t]) { adj[u].push_back(edg.to); cnt[edg.to]++; } } } queue<int> q; for (int i = 1; i <= n; i++) { if (cnt[i] == 0) { q.push(i); } } vector<int> topsort; while (!q.empty()) { int u = q.front(); q.pop(); topsort.push_back(u); for (auto &v : adj[u]) { cnt[v]--; if (cnt[v] == 0) { q.push(v); } } } reverse(topsort.begin(), topsort.end()); ll ret = INF; for (auto &u : topsort) { minU[u] = distU[u]; minV[u] = distV[u]; for (auto &v : adj[u]) { minU[u] = min(minU[u], minU[v]); minV[u] = min(minV[u], minV[v]); } ret = min({ret, distU[u] + minV[u], distV[u] + minU[u]}); } cout << ret; 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...