题面

为了随时与rainbow快速交流，Freda制造了两部传呼机。Freda和rainbow所在的地方有N座房屋、M 条双向光缆。

每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费t单位时间。

现在Freda要进行Q次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。

N座房屋通过光缆一定是连通的，并且这M条光缆有以下三类连接情况：

A：光缆不形成环，也就是光缆仅有N-1 条。
B：光缆只形成一个环，也就是光缆仅有N 条。
C：每条光缆仅在一个环中。

请你帮帮他们。

输入格式

第一行包含三个用空格隔开的整数，N、M 和Q。

接下来M行每行三个整数x、y、t，表示房屋x和y之间有一条传递时间为 t 的光缆。

最后Q行每行两个整数x、y，表示Freda想知道在x和y之间传呼最少需要多长时间。

输出格式

输出Q行，每行一个整数，表示Freda每次试验的结果。

数据范围

2≤N≤10000,
N−1≤M≤12000,
Q=10000,
1≤x,y≤N,
1≤t<32768

输入样例：

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

输出样例：

3
1

题解

我觉得蓝书 把这道题基环树这里有点不合适, 放到连通性tarjan那里是在合适不过

仙人掌图, 也就是特殊的无向图v-dcc 点双缩点罢了, 无非是一般点双缩点缩点内存在多个环, 内部不好处理

而仙人掌是缩点内只有一个环, 内部处理距离很好做

还有的区别是, 普通点双缩点,在缩点内且不为割点的点只是属于这个点双, 而不会去将 点双内部的点和缩点建边

剩下的无非是 树上LCA的板子

至于怎么处理环内距离, 你要是自己弄懂了tarjan, 看看代码也就懂了, 所以~

强烈建议先把无向图的连通那性一张学了

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

const int N = 1e4 + 5;

struct STFrom {
    static const int N = 2e4 + 5;
    int f[N][20], dep[N], lg[N], t, dis[N];//N为节点的数量
    vector<pair<int, int>>* h;
    void init(int n, vector<pair<int, int>>* H) {
        t = log2(n - 1) + 1; h = H; lg[0] = -1;
        rep(i, 1, n) dep[i] = 0, lg[i] = lg[i >> 1] + 1;
    }
    void bfs(int s) {
        queue<int> q; q.push(s); dep[s] = 1; dis[s] = 0;
        rep(i, 0, t) f[s][i] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (auto& [y, c] : h[x]) {
                if (dep[y]) continue; dis[y] = dis[x] + c;
                dep[y] = dep[x] + 1; f[y][0] = x; q.push(y);
                for (int j = 1; j <= t; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
            }
        }
    }
    int lca(int x, int y) {
        if (dep[x] > dep[y]) swap(x, y);
        for (int k = dep[y] - dep[x]; ~lg[k]; k ^= 1 << lg[k]) y = f[y][lg[k]];
        if (x == y) return x;
        per(i, lg[dep[y]], 0) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    int dist(int x, int d) {
        for (; ~lg[d]; d ^= 1 << lg[d]) x = f[x][lg[d]];
        return x;
    }
} ST;

int n, m, _, k, cas;
int dfn[N], low[N], df, st[N], top;
int sum[N << 1], d[N], vcnt, fa[N];
vector<pair<int, int>> h[N], g[N << 1];

void work(int x, int y, int c) {
    sum[y] = c; swap(sum[++vcnt + n], sum[x]);
    for (int i = y; x ^ i; i = fa[i]) sum[fa[i]] = sum[i] + d[i];
    swap(sum[x], sum[vcnt + n]);
    g[vcnt + n].emplace_back(x, 0), g[x].emplace_back(vcnt + n, 0);
    for (int i = y; x ^ i; i = fa[i]) {
        int c = min(sum[i], sum[vcnt + n] - sum[i]);
        g[vcnt + n].emplace_back(i, c), g[i].emplace_back(vcnt + n, c);
    }
}

void tarjan(int x) {
    dfn[x] = low[x] = ++df, st[++top] = x;
    for (auto& [y, c] : h[x])
        if (!dfn[y]) {
            d[y] = c; fa[y] = x; tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                for (auto& [z, c] : h[x]) if (z == st[top]) work(x, z, c);
                while (y != st[top--]);
            }
        }
        else low[x] = min(low[x], dfn[y]);
}

int main() {
    IOS; cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        h[u].emplace_back(v, c); h[v].emplace_back(u, c);
    }
    tarjan(1); ST.init(vcnt + n, g); ST.bfs(1);
    for (int i = 1; i <= k; ++i) {
        int x, y, z; cin >> x >> y; z = ST.lca(x, y);
        if (z <= n) cout << ST.dis[x] + ST.dis[y] - ST.dis[z] * 2 << '\n';
        else {
            int a = ST.dist(x, ST.dep[x] - ST.dep[z] - 1);
            int b = ST.dist(y, ST.dep[y] - ST.dep[z] - 1);
            int ans = min(abs(sum[a] - sum[b]), sum[z] - abs(sum[a] - sum[b]));
            cout << ans + ST.dis[x] - ST.dis[a] + ST.dis[y] - ST.dis[b] << '\n';
        }
    }
    return 0;
}