链接： https://www.luogu.org/problem/P5236

题意：

你有一个 $n(n<=10000)$ 个点 $m(m<=20000)$ 条边的仙人掌，有 $q(q<=10000)$ 个询问，每次询问两个点之间的距离是多少（距离即两点间的最短路径）。

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;const int maxn=100005;
const int maxm=100005;
int low[maxn],dfn[maxn],dep[maxn],cou;
int len[maxn],n,m,q,fa[maxn][18],sum[maxn][18];
int S[maxn],top,dis[maxn],ed[maxm],totp,ty[maxm];
struct Graph{int cnt,nex[maxm],to[maxm];int head[maxn],val[maxn];Graph(){memset(head,-1,sizeof(head)); cnt=0;}void add(int u,int v,int va){to[cnt]=v;nex[cnt]=head[u];val[cnt]=va; head[u]=cnt++;}
}G,Cactu;
void dfs(int u,int f){for(int i=Cactu.head[u];~i;i=Cactu.nex[i]){int v=Cactu.to[i];fa[v][0]=u,dep[v]=dep[u]+1,sum[v][0]=Cactu.val[i];dfs(v,u);}
}
void deal(int u,int v){//记录整条链的长度len[++totp]=dis[S[top]]-dis[u]+ed[S[top]];//将环上的点取出while(1){int p=S[top--];int x=dis[p]-dis[u],y=len[totp]-x;Cactu.add(totp,p,min(x,y));ty[p]=(x<=y);if(p==v) break;}Cactu.add(u,totp,0);
}
void tarjan(int u,int f){dfn[u]=low[u]=++cou;S[++top]=u;for(int i=G.head[u];~i;i=G.nex[i]){int v=G.to[i];if(v==f) continue;if(!dfn[v]){dis[v]=dis[u]+G.val[i];tarjan(v,u);//这条边为非环边 直接建图if(low[v]>dfn[u]) top--,Cactu.add(u,v,G.val[i]);//如果u和v是恰好连接一个环的边else if (low[v]==dfn[u]) deal(u,v);low[u]=min(low[u],low[v]);}//这条边连回更小的位置else low[u]=min(low[u],dfn[v]),ed[u]=G.val[i];}
}
int LCA(int x,int y){int ret=0;if(dep[x]<dep[y]) swap(x,y);for(int i=15;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])ret+=sum[x][i],x=fa[x][i];if(x==y) return ret;for(int i=15;i>=0;i--)if(fa[x][i]!=fa[y][i]&&fa[x][i]!=-1){ret=ret+sum[x][i]+sum[y][i];x=fa[x][i],y=fa[y][i];}if(fa[x][0]<=n) return sum[x][0]+sum[y][0]+ret;int a=sum[x][0],b=sum[y][0],add;if(ty[x]==ty[y]) add=min(abs(a-b),len[fa[x][0]]-abs(a-b));else add=min(a+b,len[fa[x][0]]-a-b);return ret+add;
}
int main(){scanf("%d%d%d",&n,&m,&q); totp=n;rep(i,1,m){int x,y,z;scanf("%d%d%d",&x,&y,&z);G.add(x,y,z); G.add(y,x,z);}tarjan(1,-1);dfs(1,-1);for(int j=1;j<=15;j++){for(int i=1;i<=totp;i++){sum[i][j]=sum[i][j-1]+sum[fa[i][j-1]][j-1];fa[i][j]=fa[fa[i][j-1]][j-1];}}while(q--){int u,v; scanf("%d%d",&u,&v);printf("%d\n",LCA(u,v));}return 0;
}