제출 #859170

#제출 시각아이디문제언어결과실행 시간메모리
859170rxlfd314Evacuation plan (IZhO18_plan)C++17
100 / 100
477 ms44980 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ari2 = array<int, 2>; using ari3 = array<int, 3>; using arl2 = array<ll, 2>; using arl3 = array<ll, 3>; #define vt vector #define all(x) begin(x), end(x) #define size(x) (int((x).size())) #define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d)) #define FOR(a, b, c) REP(a, b, c, 1) #define ROF(a, b, c) REP(a, b, c, -1) #define chmax(a, b) (a) = (a) > (b) ? (a) : (b) #define chmin(a, b) (a) = (a) < (b) ? (a) : (b) void solve(); signed main() { #ifndef DEBUG ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif int T = 1; //cin >> T; FOR(t, 1, T) { solve(); } } void solve() { int N, M; cin >> N >> M; vt<ari2> adj[N]; FOR(i, 1, M) { int a, b, c; cin >> a >> b >> c; adj[--a].push_back({--b, c}); adj[b].push_back({a, c}); } ll D[N]; memset(D, 0x3f, sizeof(D)); int K; cin >> K; priority_queue<arl2, vt<arl2>, greater<arl2>> pq; while (K--) { int v; cin >> v, v--; pq.push({D[v] = 0, v}); } while (size(pq)) { auto [_, i] = pq.top(); pq.pop(); for (auto [j, v] : adj[i]) if (D[i] + v < D[j]) pq.push({D[j] = D[i] + v, j}); } int Q; cin >> Q; set<int> qrys[N]; FOR(i, 0, Q-1) { int a, b; cin >> a >> b; qrys[--a].insert(i); qrys[--b].insert(i); } int uf[N]; memset(uf, -1, sizeof(uf)); function<int(int)> find = [&](int i) { return uf[i] < 0 ? i : uf[i] = find(uf[i]); }; int ord[N]; iota(ord, ord+N, 0); sort(ord, ord+N, [&](const int &a, const int &b) { return D[a] > D[b]; }); bool active[N] = {}; ll ans[Q]; FOR(x, 0, N-1) { int i = ord[x]; active[i] = true; for (auto [j, _] : adj[i]) { int a = find(i), b = find(j); if (!active[j] || a == b) continue; if (size(qrys[a]) < size(qrys[b])) swap(a, b); for (int k : qrys[b]) { if (qrys[a].count(k)) { ans[k] = D[i]; qrys[a].erase(qrys[a].find(k)); } else { qrys[a].insert(k); } } qrys[b].clear(); uf[b] = a; } } FOR(i, 0, Q-1) cout << ans[i] << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...