제출 #995690

#제출 시각아이디문제언어결과실행 시간메모리
995690AcanikolicEvacuation plan (IZhO18_plan)C++14
100 / 100
338 ms51832 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; const int N = 1e5 + 10; const int mod = 998244353; const int inf = 1e9; const int LOG = 17; vector<pair<int,int>>g[N],graf[N]; bool mark[N]; long long dist[N]; int par[N],siz[N],up[N][LOG],mn[N][LOG],val[N],in[N],out[N],timer = 0,dep[N]; int get(int x) { return (x == par[x] ? x : par[x] = get(par[x])); } void unite(int u,int v) { u = get(u); v = get(v); if(u == v) return; if(siz[u] > siz[v]) swap(u,v); siz[v] += siz[u]; par[u] = v; } bool same(int u,int v) { return get(u) == get(v); } bool cmp(array<int,3>A,array<int,3>B) { return A[2] > B[2]; } void dfs(int x,int par) { dep[x] = dep[par] + 1; in[x] = ++timer; up[x][0] = par; mn[x][0] = val[x]; for(int j = 1; j < LOG; j++) { up[x][j] = up[up[x][j - 1]][j - 1]; mn[x][j] = min(mn[x][j - 1],mn[up[x][j - 1]][j - 1]); } for(auto X : graf[x]) { if(X.F == par) continue; val[X.F] = X.S; dfs(X.F,x); } out[x] = timer; } bool intree(int u,int v) { return in[u] <= in[v] && out[u] >= out[v]; } int lca(int u,int v) { if(intree(u,v)) return u; if(intree(v,u)) return v; for(int j = LOG - 1; j >= 0; j--) { if(up[u][j] > 0 && !intree(up[u][j],v)) u = up[u][j]; } return up[u][0]; } int get(int u,int LCA) { int k = dep[u] - dep[LCA],res = inf; for(int j = 0; j < LOG; j++) { if((1 << j) & k) { res = min(res,mn[u][j]); u = up[u][j]; } } return res; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; for(int i = 1; i <= n; i++) { dist[i] = inf; par[i] = i; siz[i] = 1; } vector<array<int,3>>edges; vector<pair<int,int>>vec; for(int i = 1; i <= m; i++) { int u,v,w; cin >> u >> v >> w; vec.pb({u,v}); g[u].pb({v,w}); g[v].pb({u,w}); } int k; cin >> k; priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq; for(int i = 1; i <= k; i++) { int x; cin >> x; mark[x] = true; pq.push({0,x}); dist[x] = 0; } while(!pq.empty()) { long long dst = pq.top().F; int u = pq.top().S; pq.pop(); for(auto X : g[u]) { if(dist[X.F] > dst + X.S) { dist[X.F] = dst + X.S; pq.push({dist[X.F],X.F}); } } } for(auto X : vec) { int w = min(dist[X.F],dist[X.S]); edges.pb({X.F,X.S,w}); } sort(edges.begin(),edges.end(),cmp); for(auto X : edges) { if(!same(X[0],X[1])) { graf[X[0]].pb({X[1],X[2]}); graf[X[1]].pb({X[0],X[2]}); unite(X[0],X[1]); } } dfs(1,0); int q; cin >> q; while(q--) { int u,v; cin >> u >> v; int LCA = lca(u,v); cout << min(get(u,LCA),get(v,LCA)) << "\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...