This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
const int N = 2e6+7;
int n,m,k,q,NNP[N],root[N],level[N],par[N][20],f[N][20],l[N],d[N];
vector<int> a[N];
vector<ii> adj[N];
struct DIS {
int val;
int idx;
};
DIS dist[N];
bool quick(const DIS x,const DIS y) {
return x.val > y.val;
}
void DIJKSTRA() {
priority_queue< ii, vector<ii>, greater<ii> > dt;
for(int i=1;i<=n;i++) {
if(NNP[i] == 1) {
dist[i].val = 0;
dt.push({0,i});
}
}
while(!dt.empty()) {
int u = dt.top().se;
int value = dt.top().fi;
dt.pop();
if(dist[u].val != value) continue;
for(ii w : adj[u]) {
int v = w.se;
int he = w.fi;
if(dist[v].val > he + value) {
dist[v].val = he + value;
dt.push({dist[v].val, v});
}
}
}
}
void buildLCA() {
for(int k=1;k<=18;k++) {
for(int i=1;i<=n;i++) {
par[i][k] = par[par[i][k-1]][k-1];
f[i][k] = min(f[i][k-1], f[par[i][k-1]][k-1]);
}
}
}
void DFS(int u) {
for(int v : a[u]) {
if(par[v][0] != 0) continue;
par[v][0] = u;
l[v] = l[u] + 1;
f[v][0] = min(d[u], d[v]);
DFS(v);
}
}
int getLCA(int u,int v) {
if(l[u] < l[v]) swap(u,v);
int ans = 1e9+7;
for(int k=18;k>=0;k--) {
if(l[par[u][k]] >= l[v]) {
ans = min(ans, f[u][k]);
u = par[u][k];
}
}
if(u==v) return ans;
for(int k=18;k>=0;k--) {
if(par[u][k] != par[v][k]) {
ans = min(ans, min(f[u][k], f[v][k]));
u = par[u][k];
v = par[v][k];
}
}
return min(ans, min(f[u][0], f[v][0]));
}
int get_root(int x) {
if(root[x] == x) return x;
return get_root(root[x]);
}
bool join(int x,int y) {
int u = get_root(x);
int v = get_root(y);
if(u == v) return false;
if(level[u] > level[v]) {
root[v] = u;
level[u] += level[v];
} else {
root[u] = v;
level[v] += level[u];
}
return true;
}
void TREE() {
sort(dist+1,dist+1+n,quick);
vector<int> flag(n+1,0);
for(int i=1;i<=n;i++) {
int u = dist[i].idx;
for(ii w : adj[u]){
int v = w.se;
if(flag[v] == 1) {
if(join(u,v) == true) {
//cout<<u<<" "<<v<<'\n';
a[u].push_back(v);
a[v].push_back(u);
}
}
}
flag[u] = 1;
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) {
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({w,v});
adj[v].push_back({w,u});
}
cin>>k;
while(k--) {
int x;
cin>>x;
NNP[x] = 1;
}
for(int i=1;i<=n;i++) {
dist[i].val = 1e9+7;
dist[i].idx = i;
root[i] = i;
level[i] = 1;
}
DIJKSTRA();
for(int i=1;i<=n;i++) d[i] = dist[i].val;
TREE();
par[1][0] = 1; f[1][0] = d[1]; DFS(1);
buildLCA();
cin>>q;
while(q--) {
int u,v;
cin>>u>>v;
cout<<getLCA(u,v)<<'\n';
}
//cout<<f[1][0];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |