货车运输
显然，从一点走到另一点的路径中，最小值最大的路径一定在它的最大生成树上
所以要先求出最大生成树，再在生成树上找最近公共祖先，同时求出最小值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std; const int MAXN = ; int n,m,fa[MAXN],f[MAXN][],deep[MAXN],minn[MAXN][]; bool v[MAXN]; struct Edge{
int x;
int y;
int w;
} e[]; vector<int> son[MAXN],ww[MAXN]; bool cmp(Edge x,Edge y)
{
return x.w>y.w;
} int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
} void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
fa[i]=i;
for(int i=;i<=m;i++)
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
} void unionn(int x,int y)
{
fa[find(x)]=find(y);
} void mst()
{
sort(e+,e++m,cmp);
int t=;
for(int i=;i<=m;i++)
{
int x=e[i].x,y=e[i].y;
if(find(x)!=find(y))
{
unionn(x,y);
t++;
son[x].push_back(y);
ww[x].push_back(e[i].w);
son[y].push_back(x);
ww[y].push_back(e[i].w);
if(t==n-) break;
}
}
} void build(int now,int d)
{
v[now]=;
deep[now]=d;
for(int i=;(<<i)<=deep[now];i++)
{
minn[now][i]=min(minn[now][i-],minn[f[now][i-]][i-]);
f[now][i]=f[f[now][i-]][i-];
}
for(int i=;i<son[now].size();i++)
if(!v[son[now][i]])
{
int u=son[now][i];
minn[u][]=ww[now][i];
f[u][]=now;
build(u,d+);
}
} int lca(int x,int y)
{
int ans=0x7fffffff;
if(deep[x]!=deep[y])
{
if(deep[x]>deep[y]) swap(x,y);
for(int i=;i>=;i--)
if(deep[f[y][i]]>=deep[x])
{
ans=min(ans,minn[y][i]);
y=f[y][i];
}
}
if(x==y) return ans;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])
{
ans=min(ans,minn[x][i]);
ans=min(ans,minn[y][i]);
x=f[x][i];
y=f[y][i];
}
ans=min(ans,minn[x][]);
ans=min(ans,minn[y][]);
if(ans==0x7fffffff||ans==)
ans=-;
return ans;
} void work()
{
int q;
scanf("%d",&q);
int x,y;
while(q--)
{
scanf("%d%d",&x,&y);
if(find(x)!=find(y))
printf("-1\n");
else
printf("%d\n",lca(x,y));
}
} int main()
{
init();
mst();
for(int i=;i<=n;i++)
{
if(!v[i])
build(i,);
}
work();
return ;
}