#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
int n , m , k , d[100005] , pai[100005] , peso[100005] , fn[100005] , sparse[100005][22] , custo[100005] , anc[100005][22] , h[100005];
vector<pii> adj[100005];
struct edges{
int x , y, z;
};
bool cmp(edges a , edges b){
return a.z > b.z;
}
void pre(int i , int j){
if(i == j) h[i] = 0;
for(int y = 0 ; y < adj[i].size();y++){
pii v = adj[i][y];
if(v.S == j) continue;
fn[v.S] = i;
custo[v.S] = v.F;
h[v.S] = h[i] + 1;
pre(v.S , i);
}
}
int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]);}
void join(int u , int v){
u = fd(u) , v = fd(v);
if(peso[u] > peso[v]) swap(u,v);
pai[u] = v, peso[v] += peso[u] + 1;
}
int query(int x , int y){
if(h[x] < h[y]) swap(x,y);
int ansj = 1000000000;
for(int i = 21 ; i >= 0 ; i--){
while(h[x] >= h[y] + (1<<i)){
ansj = min(ansj , sparse[x][i]);
x = anc[x][i];
}
}
if(x == y) return ansj;
for(int i = 21 ; i >= 0 ; i--){
if(anc[x][i] != anc[y][i] && anc[x][i] != -1){
ansj = min(ansj , sparse[x][i]);
ansj = min(ansj , sparse[y][i]);
x = anc[x][i] , y = anc[y][i];
}
}
ansj = min(ansj , sparse[x][0]);
ansj = min(ansj , sparse[y][0]);
return ansj;
}
int main(){
scanf("%d%d" , &n, &m);
vector<edges> v;
for(int i = 0 ; i <n;i++){
pai[i] = i , peso[i] = 0 , d[i] = (int) 1e9;
}
for(int i = 0 ; i < m ; i++){
int x,y,z;
scanf("%d%d%d" , &x , &y , &z);
x--, y--;
v.pb({x,y,z});
adj[x].pb(pii(z,y));
adj[y].pb(pii(z,x));
}
scanf("%d" , &k);
priority_queue<pii , vector<pii> , greater<pii> > pq;
for(int i = 0 ; i < k ; i++) {
int x;
scanf("%d" , &x);
x--;
d[x] = 0;
pq.push(pii(0,x));
}
while(!pq.empty()){
pii u = pq.top();
pq.pop();
if(d[u.S] != u.F) continue;
for(int j = 0 ; j < adj[u.S].size();j++){
pii v = adj[u.S][j];
if(d[v.S] > v.F + u.F){
d[v.S] = v.F + u.F;
pq.push(pii(d[v.S] , v.S));
}
}
}
for(int i = 0 ; i < m ; i++){
v[i].z = min(d[v[i].x] , d[v[i].y]);
adj[v[i].x].clear();
adj[v[i].y].clear();
}
sort(v.begin() , v.end() , cmp);
for(int i = 0 ; i <m;i++){
if(fd(v[i].x) != fd(v[i].y)){
join(v[i].x , v[i].y);
adj[v[i].x].pb(pii(v[i].z , v[i].y));
adj[v[i].y].pb(pii(v[i].z , v[i].x));
}
}
for(int i = 0 ; i < 100005 ; i++)
for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = 1000000009;
memset(fn , -1 , sizeof fn);
pre(0 , 0);
for(int i = 0 ; i < 100005 ; i++){
if(fn[i] != -1) anc[i][0] = fn[i] , sparse[i][0] = custo[i];
}
for(int j = 1; j < 22 ; j++){
for(int i = 0 ; i < 100005;i++){
if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j] , min(sparse[i][j-1] , sparse[anc[i][j-1]][j-1]);
}
}
int q;
scanf("%d" , &q);
while(q--){
int x,y;
scanf("%d%d" , &x , &y);
x-- ,y--;
printf("%d\n" , query(x,y));
}
}
Compilation message
plan.cpp: In function 'void pre(int, int)':
plan.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int y = 0 ; y < adj[i].size();y++){
~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:89:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[u.S].size();j++){
~~^~~~~~~~~~~~~~~~~
plan.cpp:120:146: error: expected ')' before ';' token
if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j] , min(sparse[i][j-1] , sparse[anc[i][j-1]][j-1]);
^
plan.cpp:63:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:70:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d" , &x , &y , &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:76:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &k);
~~~~~^~~~~~~~~~~
plan.cpp:80:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &x);
~~~~~^~~~~~~~~~~
plan.cpp:124:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &q);
~~~~~^~~~~~~~~~~
plan.cpp:127:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &x , &y);
~~~~~^~~~~~~~~~~~~~~~~~
