题目

给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

输入格式

输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问

输出格式

输出Q行，每行一个整数表示询问的答案

输入样例

9 10 2

1 2 1

1 4 1

3 4 1

2 3 1

3 7 1

7 8 2

7 9 2

1 5 3

1 6 4

5 6 1

1 9

5 7

输出样例

5

6

提示

对于100%的数据，N<=10000，Q<=10000

题解

仙人掌的题目，都与树上的方法相联系，再考虑环的影响

首先如果在树上，我们设d[u]表示u到根的距离，两点u，v的距离dis=d[u]+d[v]−2∗d[lca]

现在加上几个环，我们先跑一遍dfs找出所有的环以及算出d[]，然后重构树，将环上的点全部连到该环最高点上，距离为环上到最高点的最短路

这样子构建出来的树，我们可以用倍增套用树的方法求解

如果求解时两点倍增时算得的最后祖先属于同一个环，那么就考虑环的贡献

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)

using namespace std;

const int maxn = 10005,maxm = 100005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,Q,h[maxn],ne = 2;

struct EDGE{int to,nxt,w;}ed[maxm];

inline void build(int u,int v,int w){

    ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;

    ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++;

}

int h2[maxn];

struct E{int to,nxt;}e[2 * maxn];

inline void add(int u,int v){e[ne] = (E){v,h2[u]}; h2[u] = ne++;}

int dfn[maxn],low[maxn],d[maxn],dep[maxn],cnt = 0;

int fa[maxn][20],dis[maxn][20];

int cir[maxn],siz[maxn];

void getcir(int rt,int k){

    int to = ed[k].to,len = d[to] - d[rt] + ed[k].w;

    siz[++siz[0]] = len;

    for (int i = to; i != rt; i = fa[i][0]){

        add(rt,i);

        dis[i][0] = min(d[i] - d[rt],len - d[i] + d[rt]);

        cir[i] = siz[0];

    }

}

void dfs(int u){

    dfn[u] = low[u] = ++cnt; int to;

    Redge(u) if ((to = ed[k].to) != fa[u][0]){

        if (!dfn[to]){

            fa[to][0] = u;

            d[to] = d[u] + ed[k].w;

            dfs(to);

            low[u] = min(low[u],low[to]);

        }else low[u] = min(low[u],dfn[to]);

        if (dfn[u] < low[to]) add(u,to),dis[to][0] = ed[k].w;

    }

    Redge(u) if (fa[to = ed[k].to][0] != u && dfn[u] < dfn[to])

        getcir(u,k);

}

void dfs2(int u){

    REP(i,15){

        fa[u][i] = fa[fa[u][i - 1]][i - 1];

        dis[u][i] = dis[u][i - 1] + dis[fa[u][i - 1]][i - 1];

    }

    for (int k = h2[u],to; k; k = e[k].nxt){

        fa[to = e[k].to][0] = u; dep[to] = dep[u] + 1;

        dfs2(to);

    }

}

int solve(int u,int v){

    if (dep[u] < dep[v]) swap(u,v);

    int ans = 0,D = dep[u] - dep[v];

    for (int i = 0; (1 << i) <= D; i++)

        if ((1 << i) & D) ans += dis[u][i],u = fa[u][i];

    if (u == v) return ans;

    for (int i = 15; i >= 0; i--)

        if (fa[u][i] != fa[v][i]){

            ans += dis[u][i] + dis[v][i];

            u = fa[u][i]; v = fa[v][i];

        }

    if (cir[u] && cir[u] == cir[v])

        ans += min(abs(d[u] - d[v]),siz[cir[u]] - abs(d[u] - d[v]));

    else ans += dis[u][0] + dis[v][0];

    return ans;

}

int main(){

    N = RD(); M = RD(); Q = RD(); int a,b,w;

    while (M--) a = RD(),b = RD(),w = RD(),build(a,b,w);

    ne = 1;

    dfs(1);

    dep[1] = 1;

    dfs2(1);

    while (Q--){

        a = RD(); b = RD();

        printf("%d\n",solve(a,b));

    }

    return 0;

}