最短路问题

解题思路

本题要求仙人掌图中任意两个点之间的最短路径，由于仙人掌图是一棵特殊的树，所以我们先考虑一个简单的问题，在一棵树中任何求任意两个点之间的最短路径。

由于一棵树上任意两点之间的路径是唯一确定的，因此如果我们想求任意两点之间的最短路，其实就是求任意两点之间的权值和。这就可以用最近公共祖先 $+$ 树上差分来求。

对于任意一条路径 $(a, b)$，设 $p$ 是 $a, b$ 的最近公共祖先，$d_i$ 表示 $i$ 到根节点的路径上的权值之和。则路径 $(a, b)$ 的权值和就是 $d_a+d_b-2 \cdot d_p$。

但是本题本身不是一棵树，因此我们需要先将仙人掌转化成一棵圆方树，这样我们就可以在圆方树中用 $LCA$ 来求任意两个点之间的最短距离了。

对于原图中 $(a, b)$ 之间的路径，我们设 $p$ 是 $a, b$ 的最近公共祖先。此时如果 $p$ 是圆点，那么此时 $p$ 到 $a$ 的路径一共分为两个部分，一部分是 $p$ 走到 $a$ 所在的环之前的环外边，这些边和原图中的边是一一对应的，不需要考虑，另一部分则是从 $a$ 所在环的头节点走到 $a$ 之间的路径，由于这一条路径的权值恰好是原图中从头节点走到 $a$ 的最短路径，因此也不需要考虑。如果路径中还需要经过其他的环，同样能证明路径中的权值和是相等的，同理 $p$ 到 $b$ 的路径也可以这样分析。由此可以发现当 $p$ 是圆点时，直接用 $LCA$ 求路径上的权值和即可。

这里还有一个细节，就是 $a, b$ 不可能在同一个环中，如果在同一个环中，那么 $p$ 就不可能是圆点，只能是方点，而如果 $a, b$ 不在同一个环中，则 $a, b$ 之间的路径就一定经过 $p$，所以我们才能将 $a$ 到 $b$ 之间的路径分成 $p$ 到 $a$ 和 $p$ 到 $b$ 来分别考虑。

另一种情况是 $p$ 是方点，如果 $a, b$ 的最近公共祖先是方点，那么 $a$ 和 $b$ 往上走时，他们的交汇点一定在某个环上。即 $a$ 和 $b$ 往上走会同时走到一个环上，并且走到的这两个环上的点一定不是这个环的头节点，否则 $p$ 就是头节点而不是方点。假设 $a$ 往上走到环上的点 $c$，$b$ 往上走到环上的点 $d$，此时 $a$ 到 $c$ 的路径和 $b$ 到 $d$ 的路径可以按照上面的思路直接求，此时我们还需要求 $c$ 到 $d$ 的路径的最短距离，这里就有两种情况了，因为 $c$ 和 $d$ 此时都在环上，因此 $c$ 到 $d$ 的路径有两种，此时我们需要将两种路径的距离取一个最小值。然后再加上剩下两个部分的路径，就是 $a$ 到 $b$ 的最短路径了。

以上就是本题的全部思路，我们将仙人掌变成圆方树然后用 $LCA$ 求任意两点之间的最短距离，注意这里需要判断最近公共祖先是圆点还是方点，进行对应的处理。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 12010, M = 36010;

int n, m, Q, new_n;
int h1[N], h2[N], e[M], w[M], ne[M], idx; //邻接表
int dfn[N], low[N], timestamp;
int s[N], stot[N]; //s 表示每个点到所在环头节点的权值前缀和，stot 表示每个点所在环的总长度
int fu[N], fw[N], fe[N]; //fu 表示每个点的父节点，fw 表示每个点和父节点之间的边的权值，fe 表示每个点是从哪条边走过来的
int d[N]; //d 表示每个点到根节点的距离
int fa[N][14], depth[N]; //lca 数组
int A, B;

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

//找出从 x -> y 的简单环，x 和 y 之间的边权值为 z，x 是头节点
void build_circle(int x, int y, int z)
{
    int sum = z;
    for(int k = y; k != x; k = fu[k]) //从 y 沿着父节点遍历环中所有点
    {
        s[k] = sum;
        sum += fw[k];
    }
    s[x] = stot[x] = sum;

    add(h2, x, ++new_n, 0); //从头节点向方点连一条权值是 0 的边
    for(int k = y; k != x; k = fu[k])
    {
        stot[k] = sum;
        add(h2, new_n, k, min(s[k], sum - s[k])); //从方点向所有圆点连边
    }
}

void tarjan(int u, int from) //建圆方树
{
    dfn[u] = low[u] = ++timestamp;
    for(int i = h1[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            fu[j] = u, fw[j] = w[i], fe[j] = i; //fe 用来防止重边问题
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if(dfn[u] < low[j]) add(h2, u, j, w[i]); //桥不在任意一个环上，环外边直接加上
        }
        else if(i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }

    //求一下从 u 出发的所有简单环
    for(int i = h1[u]; i != -1; i = ne[i]) //枚举 u 的所有子节点，找出走回来的点
    {
        int j = e[i];
        //如果 j 在 u 的下面且不是从 u 走过来的，说明 j 是回到 u 的点，即找到一个简单环
        if(dfn[u] < dfn[j] && fe[j] != i)
            build_circle(u, j, w[i]);
    }
}

void dfs_lca(int u, int father) //预处理 lca
{
    depth[u] = depth[father] + 1;
    fa[u][0] = father;

    for(int k = 1; k <= 13; k++)
        fa[u][k] = fa[fa[u][k - 1]][k - 1];
    for(int i = h2[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        d[j] = d[u] + w[i];
        dfs_lca(j, u);
    }
}

int lca(int a, int b) //求 a 和 b 的最近公共祖先 p，并记录 a 和 b 差一步走到 p 的位置 A 和 B
{
    if(depth[a] < depth[b]) swap(a, b);

    for(int k = 13; k >= 0; k--)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if(a == b) return a;

    for(int k = 13; k >= 0; k--)
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    A = a, B = b;
    return fa[a][0];
}

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

    new_n = n; //用来给所有方点编号
    memset(h1, -1, sizeof h1); //初始化仙人掌
    memset(h2, -1, sizeof h2); //初始化圆方树

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h1, a, b, c), add(h1, b, a, c); //无向边
    }

    tarjan(1, -1); //建圆方树
    dfs_lca(1, 0); //预处理 lca

    while(Q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if(p <= n) printf("%d\n", d[a] + d[b] - 2 * d[p]); //如果 p 是圆点，直接输出
        else //否则 p 是方点，需要分三段求
        {
            int da = d[a] - d[A], db = d[b] - d[B]; //a -> A、b -> B
            int l = abs(s[A] - s[B]);
            int dm = min(l, stot[A] - l); //A -> B
            printf("%d\n", da + dm + db);
        }
    }

    return 0;
}