제출 #1021336

#제출 시각아이디문제언어결과실행 시간메모리
1021336aufanEvacuation plan (IZhO18_plan)C++17
29 / 100
1063 ms60784 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; const int inff = 1e18; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> v(n + 1); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; v[a].push_back({b, c}); v[b].push_back({a, c}); } int k; cin >> k; vector<int> dist(n + 1, inff); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int i = 0; i < k; i++) { int x; cin >> x; dist[x] = 0; pq.push({dist[x], x}); } while (!pq.empty()) { auto [w, x] = pq.top(); pq.pop(); if (w > dist[x]) continue; for (auto [z, c] : v[x]) { if (w + c < dist[z]) { dist[z] = w + c; pq.push({dist[z], z}); } } } vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int x, int y) { return dist[x] > dist[y]; }); int q; cin >> q; vector<vector<array<int, 5>>> qr(n); for (int i = 0; i < q; i++) { int a, b; cin >> a >> b; int lo = 0, hi = n - 1; qr[(lo + hi) / 2].push_back({lo, hi, a, b, i}); } vector<int> ans(q); for (int _ = 0; _ < 20; _++) { vector<int> par(n + 1), sz(n + 1, 1); iota(par.begin(), par.end(), 0); function<int(int)> root = [&](int x) { return par[x] == x ? x : par[x] = root(par[x]); }; auto join = [&](int x, int y) { x = root(x); y = root(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; par[y] = x; }; auto check = [&](int x, int y) { return root(x) == root(y); }; vector<vector<array<int, 5>>> tmp(n); for (int i = 0; i < n; i++) { int x = ord[i]; for (auto [z, c] : v[x]) { if (dist[z] >= dist[x]) { join(x, z); } } for (auto &[lo, hi, a, b, j] : qr[i]) { if (check(a, b)) { ans[j] = dist[x]; hi = i - 1; } else { lo = i + 1; } if (lo <= hi) tmp[(lo + hi) / 2].push_back({lo, hi, a, b, j}); } } swap(qr, tmp); } for (int i = 0; i < q; i++) cout << ans[i] << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...