結果
問題 | No.1442 I-wate Shortest Path Problem |
ユーザー |
![]() |
提出日時 | 2021-03-26 22:30:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 935 ms / 3,000 ms |
コード長 | 2,681 bytes |
コンパイル時間 | 2,338 ms |
コンパイル使用メモリ | 196,652 KB |
実行使用メモリ | 36,800 KB |
最終ジャッジ日時 | 2024-11-29 00:07:21 |
合計ジャッジ時間 | 15,733 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int LOG = 17; const long long INF = 1000000000000000; int main(){ int N, K; cin >> N >> K; vector<vector<pair<int, int>>> E(N); for (int i = 0; i < N - 1; i++){ int A, B, C; cin >> A >> B >> C; A--; B--; C *= 2; E[A].push_back(make_pair(C, B)); E[B].push_back(make_pair(C, A)); } vector<vector<pair<int, int>>> E2 = E; for (int i = 0; i < K; i++){ E2.push_back(vector<pair<int, int>>(0)); } for (int i = 0; i < K; i++){ int M, P; cin >> M >> P; for (int j = 0; j < M; j++){ int X; cin >> X; X--; E2[X].push_back(make_pair(P, N + i)); E2[N + i].push_back(make_pair(P, X)); } } vector<vector<long long>> d(K, vector<long long>(N + K, -1)); for (int i = 0; i < K; i++){ priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; pq.push(make_pair(0, N + i)); while (!pq.empty()){ long long dd = pq.top().first; int v = pq.top().second; pq.pop(); if (d[i][v] == -1){ d[i][v] = dd; for (auto P : E2[v]){ int w = P.second; if (d[i][w] == -1){ pq.push(make_pair(dd + P.first, w)); } } } } } vector<int> p(N, -1); vector<vector<int>> c(N); vector<long long> d1(N, 0); vector<int> d2(N, 0); queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (auto P : E[v]){ int w = P.second; if (w != p[v]){ p[w] = v; c[v].push_back(w); d1[w] = d1[v] + P.first; d2[w] = d2[v] + 1; q.push(w); } } } vector<vector<int>> pp(LOG, vector<int>(N, -1)); pp[0] = p; for (int i = 0; i < LOG - 1; i++){ for (int j = 0; j < N; j++){ if (pp[i][j] != -1){ pp[i + 1][j] = pp[i][pp[i][j]]; } } } int Q; cin >> Q; for (int i = 0; i < Q; i++){ int U, V; cin >> U >> V; U--; V--; long long ans = INF; for (int j = 0; j < K; j++){ for (int k = 0; k < K; k++){ ans = min(ans, d[j][U] + d[k][V] + d[j][N + k]); } } int u = U, v = V; if (d2[U] > d2[V]){ swap(U, V); } for (int j = 0; j < LOG; j++){ if (((d2[V] - d2[U]) >> j & 1) == 1){ V = pp[j][V]; } } int w; if (U == V){ w = U; } else { for (int i = LOG - 1; i >= 0; i--){ if (pp[i][U] != pp[i][V]){ U = pp[i][U]; V = pp[i][V]; } } w = p[U]; } ans = min(ans, d1[u] + d1[v] - 2 * d1[w]); ans /= 2; cout << ans << endl; } }