제출 #1262313

#제출 시각아이디문제언어결과실행 시간메모리
12623134QT0RCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
192 ms20936 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; ll N, M, S, T, U, V; vector<vector<pll>> graph; vector<ll> lider; vector<ll> siz; const ll oo = 1e18; ll Find(ll v) { if (lider[v] == v) return v; return lider[v] = Find(lider[v]); } void Union(ll a, ll b) { a = Find(a); b = Find(b); if (a == b) return; if (siz[a] < siz[b]) swap(a, b); lider[b] = a; siz[a] += siz[b]; } vector<ll> Dijkstra(ll st) { priority_queue<pll, vector<pll>, greater<pll>> pq; vector<ll> dist(N + 1, oo); dist[st] = 0; pq.push({0, st}); while (pq.size()) { auto [d, v] = pq.top(); pq.pop(); if (d != dist[v]) continue; for (auto [u, c] : graph[v]) { if (Find(v) == Find(u)) c = 0; if (d + c < dist[u]) { dist[u] = d + c; pq.push({dist[u], u}); } } } return dist; } void init() { cin >> N >> M >> S >> T >> U >> V; graph.resize(N + 1); siz.resize(N + 1, 1); lider.resize(N + 1); iota(lider.begin(), lider.end(), 0); for (ll i = 1, a, b, c; i <= M; i++) { cin >> a >> b >> c; graph[a].push_back({b, c}); graph[b].push_back({a, c}); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); init(); vector<ll> dist_from_S = Dijkstra(S); vector<ll> dist_from_T = Dijkstra(T); vector<ll> dist_from_U = Dijkstra(U); for (ll v = 1; v <= N; v++) { for (auto [u, c] : graph[v]) { if ((dist_from_S[v] + c + dist_from_T[u]) == dist_from_S[T]) Union(v, u); } } vector<ll> dist_from_V = Dijkstra(V); cout << min(dist_from_U[V], dist_from_V[U]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...