1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,i,x,y,k;
int f[10010],h[10010];
bool v[10010];
int fa[10010][32],b[10010][32];
vector <int> L[10010],d[10010];
struct {
int a,b,c;
}l[50050];
inline bool cmp(Marvolo x,Marvolo y){return x.c>y.c;}
inline int find(int x){return (f[x]==x)?x:f[x]=find(f[x]);}
inline void swap(int &e,int &r){int t=e; e=r; r=t;}
inline int min(int a,int b){return (a<b)?a:b;}
inline void MakeMaxtree(){
int i=0,q=0,w=0;
for (i=1;i<=n;i++) f[i]=i;
for (i=1;i<=m;i++){
q=find(l[i].a); w=find(l[i].b);
if (q==w) continue;
f[q]=w;
L[l[i].a].push_back(l[i].b); L[l[i].b].push_back(l[i].a);
d[l[i].a].push_back(l[i].c); d[l[i].b].push_back(l[i].c);
}
return;
}
inline void Maketree(int x){
int i=0;
v[x]=1;
if (L[x].size()!=0)
for (i=0;i<L[x].size();i++)
if (!v[L[x][i]]) {
fa[L[x][i]][0]=x; b[L[x][i]][0]=d[x][i];
h[L[x][i]]=h[x]+1;
Maketree(L[x][i]);
}
return;
}
inline void Ready(){
int i=0,j=0;
h[1]=1;
MakeMaxtree(); Maketree(1);
for (j=1;j<=30;j++)
for (i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
b[i][j]=min(b[i][j-1],b[fa[i][j-1]][j-1]);
}
return;
}
inline int lca(int u,int v){
int i=0,ans=0x3f3f3f3f,d=0;
if (h[u]<h[v]) swap(u,v);
d=h[u]-h[v];
for (i=0;i<=30;i++)
if ((1<<i)&d) {ans=min(ans,b[u][i]); u=fa[u][i];}
if (u==v) goto E;
for (i=29;i>=0;i--)
if (fa[u][i]!=fa[v][i]){
ans=min(ans,b[u][i]); ans=min(ans,b[v][i]);
u=fa[u][i]; v=fa[v][i];
}
ans=min(ans,b[u][0]); ans=min(ans,b[v][0]);
u=fa[u][0];
E:
return ans;
}
inline void Work(){
int i=0;
scanf("%d",&k);
for (i=1;i<=k;i++){
scanf("%d%d",&x,&y);
if (find(x)!=find(y)) {printf("-1n"); goto END;}
printf("%dn",lca(x,y));
END:;
}
return;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
scanf("%d%d%d",&l[i].a,&l[i].b,&l[i].c);
sort(l+1,l+1+m,cmp);
Ready();
Work();
return 0;
}
|
近期评论