传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3047
http://www.lydsy.com/JudgeOnline/problem.php?id=2125
双倍经验题
题意很简单，求仙人掌两点间距离
各种情况讨论了我一天多...
在膜拜了一种新的建图方式后终于思路清晰了
思路：首先树上的很好搞，dis[x]+dis[y]-2*dis[lca(x,y)]
先用SPFA求出1号点到任意点的距离dis[x]，这个待会求答案时要用
仙人掌也是一种植物，所以我们要把他变成一棵树
dfs时把每个简单环取出，每个环总有一个dfn最小的点，把它记做这个环的根
把所有环上的点向环根连边，记录它属于哪个环bel[x]（根不记录，因为它还有可能是另一个环的节点），顺便求出环的长度
环边去掉，其他边不变，这就形成了一棵树
这棵树有什么用呢？
首先这棵树上的点没有变，只是边较原仙人掌有所变化
那么我们就可以求任意两点x,y,的lca了
接下来就是愉悦的分类讨论了
设dep[x]>dep[y]
分别记录x和y的祖先且是lca的儿子的点fx和fy
1.x和y中一个是lca
画图可知这个lca是不是原图的环都没有关系
直接return dis[x]-dis[y]
2.fx和fy都在同一个环上
即bel[x]!=0&&bel[x]==bel[y]
那么ans=dis[x]-dis[fx]+dis[y]-dis[fy]+d，d是fx,和fy在环上的距离
这个画图也能知道
d怎么求，可以在dfs时得到每个点的另一个距离rdis，这个rdis不是到1的最小距离，而是每个环都按一个方向走的距离
或者你可以在取环的时候顺便求出环上点到环根的一个方向的距离rdis，这种更好理解一些，虽然我脑子一抽用了上一种方法
这样就满足可减了，可以直接用abs(rdis[fx]-rdis[fy])得出fx和fy在环上的一段距离，用len[bel[fx]]-d可得另一种距离，取min即可
3.fx和fy有一个不在环上或x和y不在同一个环上
这个简单，画图即可 ans=dis[x]+dis[y]-dis[lca]*2
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define abs(a) (a>0?a:(-(a)))
const int maxn=50010,maxm=100010,maxk=22;
using namespace std;
int n,m,Q,dis[maxn],head,tail,q[maxm+10],sta[maxn],top,rdis[maxn],rcnt,fa[maxn][maxk],dfn[maxn],last[maxn],bel[maxn],rlen[maxn],dep[maxn];
int pre[maxm],now[maxn],son[maxm],val[maxn],tot,tim;bool bo[maxn],del[maxm],vis[maxn];
void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
void ins(int a,int b,int c){add(a,b,c),add(b,a,c);}
void spfa(){
memset(dis,63,sizeof(dis));
head=dis[1]=0,q[tail=1]=1,bo[1]=1;
while (head<=tail){
if (++head>maxm) head=1;
int x=q[head];
for (int y=now[x];y;y=pre[y]){
if (dis[son[y]]>dis[x]+val[y]){
dis[son[y]]=dis[x]+val[y];
if (!bo[son[y]]){
if (++tail>maxm) tail=1;
q[tail]=son[y],bo[son[y]]=1;
}
}
}
bo[x]=0;
}
}
void getring(int st,int ed,int id){
del[id]=del[id^1]=1,rlen[++rcnt]+=val[id];
for (int x=ed;x!=st;x=son[last[x]^1]){
bel[x]=rcnt,del[last[x]]=del[last[x]^1]=1;
ins(st,x,0),rlen[rcnt]+=val[last[x]];
}
}
void dfs(int x){
dfn[x]=++tim;
for (int y=now[x];y;y=pre[y]) if (y!=(last[x]^1)&&(y<=(m*2+1))){
if (!dfn[son[y]]) last[son[y]]=y,rdis[son[y]]=rdis[x]+val[y],dfs(son[y]);
else if (dfn[son[y]]<dfn[x]) getring(son[y],x,y);
}
}
void dfs2(int x){
vis[x]=1;
for (int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int y=now[x];y;y=pre[y]) if (!del[y]&&son[y]!=fa[x][0])
dep[son[y]]=dep[x]+1,fa[son[y]][0]=x,dfs2(son[y]);
}
int query(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
//printf("step1: %d %d
",x,y);
int a=x,b=y;
for (int h=dep[x]-dep[y],i=18;h&&i>=0;i--) if (h&(1<<i)) h-=(1<<i),x=fa[x][i];
//printf("step2: %d %d
",x,y);
if (x==y) return dis[a]-dis[b];//puts("cas1:链 "),
for (int i=18;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
int lca=fa[x][0];
//if (!x||!y||!lca) return 0;
if (bel[x]&&bel[x]==bel[y]){
//puts("cas2:相同的环 ");
int d=abs(rdis[x]-rdis[y]);d=min(d,rlen[bel[x]]-d);
return dis[a]+dis[b]-dis[x]-dis[y]+d;
}
//puts("cas3：不同的环或不是环 ");
return dis[a]+dis[b]-2*dis[lca];
}
int main(){
scanf("%d%d%d",&n,&m,&Q),tot=1;
for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),ins(x,y,z);
spfa(),last[1]=-1,dfs(1),dfs2(1);
for (int i=1,x,y;i<=Q;i++) scanf("%d%d",&x,&y),printf("%d
",query(x,y));
return 0;
}
/*
13 18 3
1 2 5
2 14 3
2 9 5
14 9 2
9 15 4
9 10 6
15 10 3
10 11 7
11 12 6
12 13 5
13 10 4
2 3 2
3 4 3
4 5 2
5 6 3
6 7 2
7 8 3
8 3 2
15 12
13 2
15 12
*/