传送门
Description
给你N个点的无向连通图，图中有M条边，第j条边的长度为： d_j.
现在有 K个询问。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Input
第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Output
对每个询问，输出最长的边最小值是多少。
Sample Input
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
Sample Output
5
5
5
4
4
7
4
5
Data Constraint
50% 1<=N,M<=3000 其中30% K<=5000
100% 1 <= N <= 15,000 1 <= M <= 30,000 1 <= d_j <= 1,000,000,000 1 <= K <= 20,000
Analysis
一眼看过去就觉得是SPFA,然而，我真不知道那些用spfa的人是怎么过的
最后想了想，发现既然是求最长边权的最小值，那就用最小生成树呗
先过一遍最小生成树，然后求A-B的最短路径，怎么求呢？？？
其实很简单，既然都是棵树了，那么求LCA就好啦，边求的时候顺便求出边权的最大值就是答案了
相通了就觉得好水……
Realization
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define fin(x) freopen(""#x".in","r",stdin)
#define fout(x) freopen(""#x".out","w",stdout)
#define open(x) fin(x);fout(x)
#define ll long long
#define inf INT_MAX
struct M{
int u,v,w;
}a[30001];
int n,m,k,gx,gy,x,y,len,i,j,fa[15001],d[15001],h[80001],ft[80001],next[80001],last[80001],g[15001][17],tw[15001][17];
bool cmp(M a,M h){
return a.w<h.w;
}
int get(int k){
if(fa[k]==0) return k;
return (fa[k]=get(fa[k]));
}
void add(int x,int y,int z){
h[++len]=y;
next[len]=last[x];
last[x]=len;
ft[len]=z;
}
void dg(int k,int y){
int p=last[k];
while(p!=0){
if(h[p]!=y){
g[h[p]][0]=k;
d[h[p]]=d[k]+1;
tw[h[p]][0]=ft[p];
dg(h[p],k);
}
p=next[p];
}
}
int lca(int x,int y){
int k,ans=0;
if(d[x]<d[y]) swap(x,y);
k=trunc(log(d[x]-d[y]+1)/log(2));
while(k>=0){
if(d[g[x][k]]>d[y]) ans=max(ans,tw[x][k]),x=g[x][k];
k--;
}
if(d[x]!=d[y]) ans=max(ans,tw[x][0]),x=g[x][0];
k=trunc(log(d[x])/log(2));
while(k>=0){
if(g[x][k]!=g[y][k]) ans=max(ans,max(tw[x][k],tw[y][k])),x=g[x][k],y=g[y][k];
k--;
}
if(x==y) return ans;
else return max(ans,max(tw[x][0],tw[y][0]));
}
int main(){
scanf("%d%d%d",&n,&m,&k);
fo(i,1,m) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
sort(a+1,a+m+1,cmp);
fo(i,1,m){
gx=get(a[i].u);
gy=get(a[i].v);
if(gx!=gy){
add(a[i].u,a[i].v,a[i].w);
add(a[i].v,a[i].u,a[i].w);
fa[gx]=gy;
}
}
d[1]=1;
dg(1,0);
fo(j,1,trunc(log(n)/log(2)))
fo(i,1,n){
g[i][j]=g[g[i][j-1]][j-1];
tw[i][j]=max(tw[i][j-1],tw[g[i][j-1]][j-1]);
}
fo(i,1,k){
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
}