题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。

每一条道路对车辆都有重量限制，简称限重。

现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。 

接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路，注意：x 不等于 y，两座城市之间可能有多条道路。 

接下来一行有一个整数 q，表示有 q 辆货车需要运货。 

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市 运输货物到 y 城市，注意：x 不等于 y。

输出格式

输出共有 q

 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。

如果货车不能到达目的地，输出 −1
。
数据范围

0<n<10000
,
0<m<50000,
0<q<30000,
0≤z≤105

样例

输入样例：

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

输出样例：

3
-1
3

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define re register 
#define ll long long
const int N = 1e6 + 1;
const int INF = 1e9;
int n, m, idx, q, x, y;
int fa[N], head[N], v[N], dep[N];
int lg[N], f[N][25], dis[N][25];
struct node{
    int x, w, next;
}a[N];
struct Node{
    int x, y, w;
}e[N];
inline int read()
{
    char c = getchar();
    int f = 1,x = 0;
    while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
    return x * f;
}
inline void add(int x, int y, int w){
    a[++idx].x = y;
    a[idx].w = w;
    a[idx].next = head[x];
    head[x] = idx;
}
inline bool cmp(Node l, Node r){
    return l.w > r.w;
}
inline int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void kruskal(){
    sort(e + 1, e + m + 1, cmp);
    for(int i = 1;i <= n;i ++) fa[i] = i;
    for(int i = 1;i <= m;i ++){
        int xx = find(e[i].x);
        int yy = find(e[i].y);
        if(xx == yy) continue;
        fa[xx] = yy;
        add(xx, yy, e[i].w);
        add(yy, xx, e[i].w);
    }
    return ;
}
inline void dfs(int x, int fa){
    v[x] = 1;
    dep[x] = dep[fa] + 1;
    for(int i = 1;i <= lg[dep[x]];i ++){
        f[x][i] = f[f[x][i - 1]][i - 1];
        dis[x][i] = min(dis[x][i - 1], dis[f[x][i - 1]][i - 1]);
    }
    for(int i = head[x]; i; i = a[i].next){
        int j = a[i].x;
        if(v[j]) continue;
        f[j][0] = x;
        dis[j][0] = a[i].w;
        dfs(j, x);
    }
    return ;
}
inline int LCA(int x, int y){
    int ans = INF;
    if(find(x) != find(y)) return -1;
    if(dep[x] > dep[y]) swap(x, y);
    while(dep[y] > dep[x]){
        ans = min(ans, dis[y][lg[dep[y] - dep[x]]]);
        y = f[y][lg[dep[y] - dep[x]]];
    }
    if(x == y) return ans;
    for(int i = lg[dep[x]]; i >= 0;i --){
        if(f[x][i] != f[y][i]){
            ans = min(ans, min(dis[x][i], dis[y][i]));
            x = f[x][i];
            y = f[y][i];
        }
    }
    ans = min(ans, min(dis[x][0], dis[y][0]));
    return ans;
}
int main(){
    n = read(), m = read();
    for(int i = 1;i <= m;i ++)
        e[i].x = read(), e[i].y = read(), e[i].w = read();
    kruskal();
    lg[0] = -1;
    for(int i = 1;i <= n;i ++)
        lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= n;i ++)
        if(!v[i]){
            dfs(i, 0);
            dis[i][0] = INF;
        }
    q = read();
    for(int i = 1;i <= q;i ++){
        x = read(), y = read();
        printf("%d\n",LCA(x, y));
    }
    return 0;
}