結果
問題 | No.1442 I-wate Shortest Path Problem |
ユーザー |
|
提出日時 | 2024-01-08 23:19:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 777 ms / 3,000 ms |
コード長 | 3,689 bytes |
コンパイル時間 | 2,737 ms |
コンパイル使用メモリ | 213,876 KB |
最終ジャッジ日時 | 2025-02-18 16:35:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair<ll,ll> P; typedef vector<ll> vec; using Graph = vector<vector<ll>>; const long long INF = 1LL<<60; const long long MOD = 1000000007; // Lowest Common Ancestor by binary lifting // https://youtu.be/8uowVvQ_-Mo?t=4306 template<typename T> // T: type of cost struct lca { int n, root, l; vector<vector<int>> to; vector<vector<T>> co; vector<int> dep; vector<T> costs; vector<vector<int>> par; lca(int n):n(n),to(n),co(n),dep(n),costs(n) { l = 0; while ((1<<l) < n) ++l; par = vector<vector<int>>(n+1,vector<int>(l,n)); } void addEdge(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if (p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for (int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if (u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for (int i = 0; i < l-1; ++i) { for (int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } // LCA int LCA(int a, int b) { if (dep[a] > dep[b]) swap(a,b); int gap = dep[b]-dep[a]; for (int i = l-1; i >= 0; --i) { int len = 1<<i; if (gap >= len) { gap -= len; b = par[b][i]; } } if (a == b) return a; for (int i = l-1; i >= 0; --i) { int na = par[a][i]; int nb = par[b][i]; if (na != nb) a = na, b = nb; } return par[a][0]; } int length(int a, int b) { int c = LCA(a,b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = LCA(a,b); return costs[a]+costs[b]-costs[c]*2; } }; struct edge { ll to, cost; }; //辺 int V; //頂点数 const int MAX_V = 200000; vector<vector<edge>> G(MAX_V); ll d[MAX_V]; ll memo[10][MAX_V]; void dijkstra(int s) { //greater<P>でfirstが小さい順に取り出せる //first:最短距離,second:頂点番号 priority_queue<P, vector<P>, greater<P>> que; fill(d, d + V, INF); d[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first)continue; rep(i, G[v].size()) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n,k; cin>>n>>k; lca<ll> lca(n); rep(i,n-1){ ll a,b,c; cin>>a>>b>>c; a--;b--; G[a].push_back((edge){b,c}); G[b].push_back((edge){a,c}); lca.addEdge(a,b,c); } lca.init(); V=n+k; vec ps(k); rep(i,k){ ll m,p; cin>>m>>p; ps[i]=p; rep(j,m){ ll x;cin>>x; x--; G[x].push_back((edge){i+n,p}); G[i+n].push_back((edge){x,0}); } } rep(i,k){ dijkstra(i+n); swap(d,memo[i]); } ll q;cin>>q; rep(qi,q){ ll a,b; cin>>a>>b; a--;b--; ll ans=lca.dist(a,b); rep(i,k){ ll now=ps[i]+memo[i][a]+memo[i][b]; chmin(ans,now); } cout<<ans<<'\n'; } return 0; }