Solution

思路
先对仙人掌图建圆方树，圆圆边和原图边权一致。对于每个方点代表的环，记深度最小的点为 $x$ ， $x$ 为方点，圆方边的边权是圆点到 $x$ 的最短距离
若 $l c a (u, v)$ 为圆点，则两点间最短路转化为圆方树上 $d i s [u] + d i s [v] - 2 * d i s [l c a]$ 。（向上延伸的路径，经过环则必然经过每个方点的 $x$ ，计算无误）
若 $l c a (u, v)$ 为方点，则记 $u, v$ 在方点连接的圆点 $A, B$ 的子树内，那么两点间最短路为 $d i s [u] + d i s [v] - ∣ d i s [A] - d i s [B] ∣ + d i s (A, B)$ ， $d i s (A, B)$ 是 $A, B$ 在环上的短侧路径

Code

这题代码不会实现，就看了这份代码
这题本来应该求点双的，但这份代码里先求桥再求出环，看了好久才懂
刚开始看的时候可能会疑惑：桥的个数不是一定比割点少吗，但是它下面有一个循环，能做到不重不漏
其中 $d f n [v] > d f n [u]$ 的意思就是： $u$ 已经通过 $u$ 的某个儿子将 $v$ 遍历到，而因为 $u$ 到 $v$ 有边，所以构成了一个环

#include<bits/stdc++.h>
using namespace std;
const int N=10002,M=200002;
struct node{
	int to,ne,w;
}e[M<<1],e2[M];
int n,m,q,i,tim,dfn[N],low[N],d[N],sz[N],num,tot,tot2,h[N],h2[N],fa[N][14],dis[N][14],cir[N],dep[N],x,y,z;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
void add(int x,int y,int z){e[++tot]=(node){y,h[x],z},h[x]=tot;}
void add2(int x,int y){e2[++tot2]=(node){y,h2[x],0},h2[x]=tot2;}
void circle(int u,int v,int w){
	int len=d[v]-d[u]+w;
	sz[++num]=len;
	for (int i=v;i!=u;i=fa[i][0]){
		add2(u,i);
		cir[i]=num;
		dis[i][0]=min(d[i]-d[u],len-d[i]+d[u]);
	}
}
void tarjan(int u){
	dfn[u]=low[u]=++tim;
	for (int i=h[u],v;i;i=e[i].ne)
		if ((v=e[i].to)!=fa[u][0]){
			if (!dfn[v=e[i].to]){
				fa[v][0]=u,d[v]=d[u]+e[i].w;
				tarjan(v);
				low[u]=min(low[u],low[v]);
			}else low[u]=min(low[u],dfn[v]);
			if (low[v]>dfn[u]) add2(u,v),dis[v][0]=e[i].w;//桥
		}
	for (int i=h[u],v;i;i=e[i].ne)
		if (fa[v=e[i].to][0]!=u && dfn[v]>dfn[u]) circle(u,v,e[i].w);
}
void dfs(int u){
	for (int i=1;i<14;i++) 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 i=h2[u],v;i;i=e2[i].ne)
		if ((v=e2[i].to)!=fa[u][0]) fa[v][0]=u,dep[v]=dep[u]+1,dfs(v);
}
int solve(int x,int y){
	int ans=0;
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=13;~i;i--)
		if (dep[fa[x][i]]>=dep[y]) ans+=dis[x][i],x=fa[x][i];
	if (x==y) return ans;
	for (int i=13;~i;i--)
		if (fa[x][i]!=fa[y][i]) ans+=dis[x][i]+dis[y][i],x=fa[x][i],y=fa[y][i];
	if (cir[x] && cir[x]==cir[y]) return ans+min(abs(d[x]-d[y]),sz[cir[x]]-abs(d[x]-d[y]));
	return ans+dis[x][0]+dis[y][0];
}
int main(){
	n=rd(),m=rd(),q=rd();
	for (i=1;i<=m;i++) x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);
	tarjan(1);
	dfs(1);
	for (;q--;) x=rd(),y=rd(),wln(solve(x,y));
}

bzoj2125: 最短路

Solution

Code