bzoj2125最短路

https://www.lydsy.com/JudgeOnline/problem.php?id=2125

题意：多次询问，求仙人掌图上两点最短路。

树上两点最短路可以通过LCA求出。则考虑建出圆方树。

设$dis[u]$ 表示 $u$ 到树根的距离，则树上两点 $u,v$ 最短路为 $dis[u]+dis[v]-2\cdot dis[lca]$

圆方边的意义则是环上点到环的父亲的最短距离。

若两点 $u,v$ 的LCA是方点，则表示两点最终要经过一段弧，则此时需要求出环上某两点之间的最短路，并加上 $u,v$ 到达这个环之前经过的距离。

为了求最终的环上两点的最短距离，还要额外处理，由于之前只记录了环上点到环父亲的最短距离，而这最短距离是否经过返祖边又会影响到能否通过两个距离做差得到两点的距离，所以在处理环时还要额外记录最短距离是否经过了返祖边。

实现起来还挺烦的，一不小心就错了。

树刨求LCA和Tarjan建圆方树的fa，dfn，dis数组都不同，要格外注意。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, Q;
int nn;
struct edge
{
    int v, w;
};
vector<edge>gg[maxn], G[maxn];
void add_edge(int u, int v, int w) {
    G[u].push_back((edge) { v, w });
    G[v].push_back((edge) { u, w });
}
int dis[maxn];
int dfn[maxn], low[maxn], fa[maxn], dep[maxn];
int cnt;
int len[maxn], zn[maxn];
int S[maxn];
void solve_cir(int rt, int v, int w) {
    int top = dep[v] - dep[rt] + 1, sum = w, Dis = 0;
    for (int i = v; i != rt; i = fa[i])S[top--] = i, sum += dis[i] - dis[fa[i]];
    S[1] = rt; ++nn; top = dep[v] - dep[rt] + 1; len[nn] = sum;
    for (int i = 1; i <= top; i++) {
        int D = min(Dis, sum - Dis);
        add_edge(nn, S[i], D);
        zn[S[i]] = (D == Dis);
        Dis += dis[S[i + 1]] - dis[S[i]];
    }
}
void Tar(int u, int _fa) {
    dfn[u] = low[u] = ++cnt;
    fa[u] = _fa; dep[u] = dep[_fa] + 1;
    for (int i = 0; i < (int)gg[u].size(); i++) {
        int v = gg[u][i].v, w = gg[u][i].w;
        if (v == _fa)continue;
        if (!dfn[v]) {
            dis[v] = dis[u] + w;
            Tar(v, u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], dfn[v]);//返祖边
        if (dfn[u] < low[v]) {   //树边
            add_edge(u, v, w);
        }
    }
    for (int i = 0; i < (int)gg[u].size(); i++) {
        int v = gg[u][i].v, w = gg[u][i].w;
        if (v == _fa)continue;
        if (fa[v] != u && dfn[u] < dfn[v]) {//u在最高点处理环
            solve_cir(u, v, w);
        }
    }
}
 
int ffa[maxn], sz[maxn], son[maxn], topf[maxn], dept[maxn];
int clk, val[maxn];
void dfs1(int u, int _fa) {
    ffa[u] = _fa; sz[u] = 1; dept[u] = dept[_fa] + 1;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i].v, w = G[u][i].w;
        if (v == _fa)continue;
        dis[v] = dis[u] + w;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]])son[u] = v;
    }
}
void dfs2(int u, int topfa) {
    topf[u] = topfa; dfn[u] = ++clk; val[clk] = u;
    if (!son[u])return;
    dfs2(son[u], topfa);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i].v;
        if (v == ffa[u] || v == son[u])continue;
        dfs2(v, v);
    }
}
int LCA(int u, int v) {
    while (topf[u] != topf[v])
        dept[topf[u]] < dept[topf[v]] ? v = ffa[topf[v]] : u = ffa[topf[u]];
    return dept[u] < dept[v] ? u : v;
}
int jp(int u, int lca) {
    int res;
    while (topf[u] != topf[lca]) {
        res = topf[u], u = ffa[topf[u]];
    }
    return u == lca ? res : val[dfn[lca] + 1];
}
int query(int u, int v) {
    int lca = LCA(u, v);
    if (lca <= n)return dis[u] + dis[v] - 2 * dis[lca];
    int uu = jp(u, lca), vv = jp(v, lca);
    int d1 = dis[uu] - dis[lca], d2 = dis[vv] - dis[lca];
    if (!zn[uu])d1 = len[lca] - d1; if (!zn[vv])d2 = len[lca] - d2;//统一不走返祖边
    return dis[u] - dis[uu] + dis[v] - dis[vv] + min(abs(d1 - d2), len[lca] - abs(d1 - d2));
}
int main() {
    scanf("%d%d%d", &n, &m, &Q);
    nn = n;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        gg[u].push_back((edge) { v, w });
        gg[v].push_back((edge) { u, w });
    }
    Tar(1, 0);
    dis[1] = 0;
    dfs1(1, 0);
    dfs2(1, 1);
    while (Q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", query(u, v));
    }
    return 0;
}