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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=50010;
const int inf=0x3f3f3f3f;
int q,m,n,head[maxn],num=0,fa[maxn],vis[maxn],d[maxn],f[maxn][25],w[maxn][25];
struct edge1{
int u,v,w;
}a[maxn];
struct edge2{
int v,w,next;
}e[maxn*2];
bool cmp(const edge1&a,const edge1&b)
{
return a.w>b.w;
}
void add(int u,int v,int w)
{
e[++num].v=v;
e[num].w=w;
e[num].next=head[u];
head[u]=num;
}
int find(int x)
{
if(x!=fa[x]) return fa[x]=find(fa[x]);
return fa[x];
}
void kruskal()
{
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++)
{
if(find(a[i].u)!=find(a[i].v))
{
fa[find(a[i].u)]=find(a[i].v);
add(a[i].u,a[i].v,a[i].w);
add(a[i].v,a[i].u,a[i].w);
}
}
}
void dfs(int s)
{
vis[s]=1;
for(int i=head[s];i!=0;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
d[v]=d[s]+1;
f[v][0]=s;
w[v][0]=e[i].w;
dfs(v);
}
}
return;
}
int lca(int x,int y)
{
if(find(x)!=find(y)) return -1;
int ans=inf;
if(d[x]<d[y]) swap(x,y);
for(int i=20;i>=0;i--)
if(d[f[x][i]]>=d[y])
{
ans=min(ans,w[x][i]);
x=f[x][i];
}
if(x==y) return ans;
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
ans=min(ans,min(w[x][i],w[y][i]));
x=f[x][i];
y=f[y][i];
}
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[i].u=u;a[i].v=v;a[i].w=w;
}
scanf("%d",&q);
kruskal();
for(int i=1;i<=n;i++)
if(!vis[i])
{
d[i]=1;
dfs(i);
f[i][0]=i;
w[i][0]=inf;
}
//lac
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
{
f[j][i]=f[f[j][i-1]][i-1];
w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
}
for(int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
|