最短路
查询仙人掌两点之间的最短路。建立圆方树，圆-方之间连边为圆点到所在环顶部的最短距离，圆-圆之间连边就是原图边的距离。每个询问查询LCA,若LCA为圆点，就是这两点之间的距离，若LCA为方点，获取LCA下面两个点x,y，x和y处于一个环中，求环中两点最短距离。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10;const int M=1e5+10; struct MAP{ int head[N],ver[2*M],edge[2*M],nex[2*M],tot; inline void add(int x,int y,int z) { ver[++tot]=y,edge[tot]=z,nex[tot]=head[x],head[x]=tot; } }G,T; int n,m,q,t;//t:方点编号 //type[i]==0:圆点，如果在环中C[i]为离环顶距离沿dfs路径 //type[i]==1:方点，C[i],环的长度 int C[N],type[N]; int c[N],cnt;//环边 int dfn[N],low[N],num,stk[N],top; void tarjan(int x,int e) { dfn[x]=low[x]=++num; stk[++top]=e; for(int i=G.head[x]; i; i=G.nex[i]) { int y=G.ver[i]; if(!dfn[y]) { tarjan(y,i); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) { T.add(x,y,G.edge[i]); T.add(y,x,G.edge[i]); --top; }else if(low[y]==dfn[x]){ cnt=0;type[++t]=1; do{ c[cnt++]=stk[top];//保存环边 } while (G.ver[stk[top--]]!=y); for(int j=cnt-1;j>=0;--j)C[t]+=G.edge[c[j]]; int dis=0; for(int j=cnt-1;j>=0;--j){ dis+=G.edge[c[j]]; int v=G.ver[c[j]],mi=min(C[t]-dis,dis); C[v]=dis;T.add(t,v,mi);T.add(v,t,mi); } }//一定注意dfn[x]>dfn[y]，尾巴可能从顶部再直接访问一遍 } else if(i!=(e^1)&&dfn[x]>dfn[y]){ low[x]=min(low[x],dfn[y]); stk[++top]=i; } } } int d[N],f[N][25],max_t,dis[N]; void bfs() { max_t=log(n)/log(2)+1; d[1]=1;dis[1]=0; queue<int> q;q.push(1); while(!q.empty()) { int x=q.front();q.pop(); for(int i=T.head[x]; i; i=T.nex[i]) { int y=T.ver[i]; if(d[y])continue; d[y]=d[x]+1; dis[y]=dis[x]+T.edge[i]; f[y][0]=x; for(int i=1; i<=max_t; ++i) f[y][i]=f[f[y][i-1]][i-1]; q.push(y); } } } int cal(int x,int y) { int u=x,v=y; if(d[x]<d[y])swap(x,y); if(d[x]>d[y]) for(int i=max_t; i>=0; --i) if(d[f[x][i]]>=d[y]) x=f[x][i]; if(x==y)return dis[u]+dis[v]-2*dis[x];//一定是圆点 for(int i=max_t; i>=0; --i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; int lca=f[x][0]; if(!type[lca])return dis[u]+dis[v]-2*dis[lca]; return dis[u]+dis[v]-dis[x]-dis[y]+min(C[lca]-abs(C[x]-C[y]),abs(C[x]-C[y])); } int main(){ G.tot=T.tot=1; scanf("%d%d%d",&n,&m,&q); for(int i=0;i<m;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); G.add(x,y,z);G.add(y,x,z); } t=n; tarjan(1,0);bfs(); while(q--){ int x,y; scanf("%d%d",&x,&y); printf("%d ",cal(x,y)); } return 0; }