1. 题目

传送门＝￣ω￣＝

题目描述 Description

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description

第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出描述 Output Description

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

样例输入 Sample Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 Sample Output

3
-1
3

数据范围及提示 Data Size & Hint

对于 30% 的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
对于 60% 的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000；
对于 100% 的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。

2. 题解

很明显，这里并不要求路径最短，只要求路径上权值最小的路径权值最大，所以先跑一遍最大生成树，构建一个新的图。然后倍增求 lca，维护树上最小值。
怎么维护呢？和倍增求 lca 一个原理：设 minn[i][j] 为节点 i 到它的第 2 的 j 次方个祖先之间的权值最小的路径的权值，递推式为：minn[i][j]=min(minn[i-1][j],minn[pre[i][j-1]][j-1])，具体思路啥的见我写的倍增求 lca。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxs=10005,logs=20,inf=1000000000ll;
struct edge{int x,y,z;};
bool cmp(edge a,edge b){return a.z>b.z;}
int n,m,f[maxs],pre[maxs][logs+1],deep[maxs],minn[maxs][logs+1],q;
vector<int> g[maxs],dis[maxs];
vector<edge> e;
int findf(int a){return f[a]==a?a:f[a]=findf(f[a]);}
int read()
{
    int dig=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    return dig;
}
void dfs(int x,int p,int d)
{
    pre[x][0]=p,minn[x][0]=d;
    for(int i=1;i<=logs;i++)pre[x][i]=pre[pre[x][i-1]][i-1],minn[x][i]=min(minn[x][i-1],minn[pre[x][i-1]][i-1]);
    for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)deep[g[x][i]]=deep[x]+1,dfs(g[x][i],x,dis[x][i]);
}
void getans(int a,int b)
{
    if(findf(a)!=findf(b)){cout<<-1<<endl;return;}
    int ans=inf;
    if(deep[a]>deep[b])swap(a,b);
    for(int i=logs;i>=0;i--)if(deep[pre[b][i]]>=deep[a])ans=min(ans,minn[b][i]),b=pre[b][i];
    if(a==b){cout<<ans<<endl;return;}
    for(int i=logs;i>=0;i--)if(pre[b][i]!=pre[a][i])ans=min(ans,minn[a][i]),ans=min(ans,minn[b][i]),a=pre[a][i],b=pre[b][i];
    ans=min(ans,minn[a][0]),ans=min(ans,minn[b][0]);
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);
    n=read(),m=read();
    for(int i=0;i<=n;i++){for(int j=0;j<=logs;j++)minn[i][j]=inf,f[i]=i;}
    for(int i=1,x,y,z;i<=m;i++)x=read(),y=read(),z=read(),e.push_back((edge){x,y,z});
    sort(e.begin(),e.end(),cmp);
    for(int i=0,cnt=1;i<m&&cnt<n;i++)
    {
        int fa[2]={findf(e[i].x),findf(e[i].y)};
        if(fa[0]!=fa[1])f[fa[0]]=fa[1],g[e[i].x].push_back(e[i].y),g[e[i].y].push_back(e[i].x),dis[e[i].x].push_back(e[i].z),dis[e[i].y].push_back(e[i].z),cnt++;
    }
    for(int i=1;i<=n;i++)if(!deep[i])dfs(i,0,inf);
    q=read();
    for(int i=1,a,b;i<=q;i++)a=read(),b=read(),getans(a,b);
    return 0;
}