网络稳定性 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int Log = 20;
const int maxn = 300000 + 100;
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

bool operator<(const Edge &a, const Edge &b) {
    return a.w > b.w;
}

struct Node {
    int pos, dis;
    Node() {}
    Node(int pos, int dis) : pos(pos), dis(dis) {}
};

int n, m, q, u, v, w, idCnt;
int fa[maxn], id[maxn];
bool vis[maxn];
Edge edge[maxn];
vector<Node> G[maxn];
int st[maxn][Log], disSt[maxn][Log];

void init() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}

int Find(int x) {
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void union_(int x, int y) {
    fa[Find(x)] = Find(y);
}

void dfs(int root, int fa, int dis) {
    vis[root] = true;
    id[root] = ++idCnt;
    st[root][0] = fa;
    disSt[root][0] = dis;
    for(int j = 1; j < Log; ++j) {
        st[root][j] = st[st[root][j - 1]][j - 1];
        disSt[root][j] = min(disSt[root][j - 1], disSt[st[root][j - 1]][j - 1]);
    }
    for (Node &node : G[root]) {
        int pos = node.pos;
        int dis = node.dis;
        if (pos != fa) {
            dfs(pos, root, dis);
        }
    }
}

int lca(int x, int y) {
    if(x == y) {
        return x;
    }
    if(id[x] > id[y]) {
        swap(x, y);
    }
    for(int i = Log - 1; i >= 0; --i) {
        if(id[st[y][i]] > id[x]) {
            y = st[y][i];
        }
    }
    return st[y][0];
}

int lcaDis(int f, int u) {
    int ret = INT_MAX;
    if (f == u) {
        return ret;
    }
    for (int i = Log - 1; i >= 0; --i) {
        if (id[st[u][i]] > id[f]) {
            ret = min(ret, disSt[u][i]);
            u = st[u][i];
        }
    }
    return min(ret, disSt[u][0]);
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n >> m >> q;
    for (int i = 0; i < m; ++i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    init();
    sort(edge, edge + m);
    for (int i = 0; i < m; ++i) {
        u = edge[i].u;
        v = edge[i].v;
        w = edge[i].w;
        if (Find(u) != Find(v)) {
            union_(u, v);
            G[u].push_back(Node(v, w));
            G[v].push_back(Node(u, w));
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i, i, 0);
        }
    }
    while (q--) {
        cin >> u >> v;
        if (Find(u) != Find(v)) {
            cout << -1 << endl;
            continue;
        }
        int f = lca(u, v);
        cout << min(lcaDis(f, u), lcaDis(f, v)) << endl;
    }

    return 0;
}