最大生成树+LCA $O(nlogn)$

$一条路的稳定度是整条路径中权重最小的那个，一条两点之间的通信稳定度是所有路径稳定度最高的那个\\ 因此我们要找两点之间的权重最大的边组成的路径，而最终表示这条路径的稳定度是其中的最小边权\\ 找到两点之间的最大版权用最大生成树Kruskal, O(mlogm)可以实现预处理出来\\ 找两点之间的最小权重，dfs的话O(n)加上询问的话就是O(qn) = O(n^2)超时\\ 需要优化找最下边权的操作，这里采用LCA处理节点到根节点的最短边权\\ 建LCA \ O(nlogn)提前预处理 查询O(logn)$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> PII;

const int N = 100010, M = 2 * N;

struct Edge{
    int a, b, c;
    bool operator< (const Edge& o) const{
        return c > o.c;
    }
}edge[3 * N];
int p[N]; 
int n, m, q;
int h[N], e[M], w[M], ne[M], idx;
int depth[N], f[N][16], dp[N][16];//dp[i][j]表示从i往上条2^j (不含i + 2^j)步内的最小边

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int find(int x){
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void kruskal(){
    sort(edge, edge + m);
    for (int i = 0; i <= n; i ++) p[i] = i;

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++){
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        int fa = find(a), fb = find(b);
        if (fa != fb){
            add(a, b, c); add(b, a, c);
            p[fa] = fb;
        }
    }
}

void bfs(int root){
    memset(depth, 0x3f, sizeof depth);
    queue<int> q;
    q.push(root);
    depth[root] = 1; depth[0] = 0;

    while (q.size()){
        auto t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]){
            int j = e[i];

            if (depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                f[j][0] = t;
                dp[j][0] = w[i];

                q.push(j);

                for (int k = 1; k <= 15; k ++){
                    f[j][k] = f[f[j][k - 1]][k - 1];
                    dp[j][k] = min(dp[j][k - 1], dp[f[j][k - 1]][k - 1]);
                }
            }
        }
    }
}

int lca(int a, int b){
    int res = 0x3f3f3f3f;
    if (depth[a] < depth[b]) return lca(b, a);

    for (int i = 15; i >= 0; i --){//从大到小枚举，先比较二进制高位
        if (depth[f[a][i]] >= depth[b]){
            res = min(res, dp[a][i]);
            a = f[a][i];
        }
    }
    if (a == b) return res;

    for (int i = 15; i >= 0; i --){
        if (f[a][i] != f[b][i]){
            res = min(res, min(dp[a][i], dp[b][i]));
            a = f[a][i];
            b = f[b][i];
        }
    }
    return min(res, min(dp[a][0], dp[b][0]));
}

int main(){
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 0; i < m; i ++){
        scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c);
    }
    kruskal();
    bfs(e[0]);

    while (q --){
        int a, b;
        scanf("%d%d", &a, &b);
        int res = lca(a, b);
        if (res > 0) printf("%d\n", res);
        else puts("-1");
    }

    return 0;
}