这是仙人掌的模板题，仙人掌不能有自环，但是可以有重边。多颗仙人掌组成的图叫做沙漠。将仙人掌的每个环缩成一个点之后，就会形成树
仙人掌转树要利用圆方树：
①.任选一个点为根
②.此时每个环有且仅有唯一一个点到根的距离最近。然后将环中的点分类，离根节点最近的点叫“头”，剩余的点作为一类。接下来要将环变形。对于一个环，新建立一个方点，然后从头向方点连边（权值为\(0\)），方点向环上剩余的点连边（设某个剩余的点为\(x\)，权值为“头”到\(x\)的最短距离），于是就将一个环拆成了一棵树，如下
③.分类讨论。一个自然的想法就是求\(x,y\)在圆方树上的最近公共祖先\(p\)，然后在树上求两者的最短距离。如果说\(p\)是圆点的话是成立的（此时\(x,y\)要么不在一个环里且\(x,y\)之间的（在原图的）路径必经过\(p\)或者\(x,y\)在一个环里且\(x\)或\(y\)就是\(p\)）；如果\(p\)是方点的话，就说明\(x,y\)在原图的路径会先走到同一个环上的两个非头点（因为圆方树中\(p\)为方点，就说明从两个不是交汇环的非头点走到\(p\)），然后再在这个环上从一个非头点走到另一个非头点。前者可以用\(p\)是圆点的思路求，后者求出环上两条路径取更小值就好了。举个例子
然后对应到圆方树上的\(x,y\)就清楚了
以上就是仙人掌转圆方树的三个步骤，都是这么做的
实现细节：
一.原图当中一个环就是一个v-DCC
二.找头的时候，就是从根节点直接遍历，遍历到的第一个点就是头
上面的写法是狭义圆方树，其实更一般的写法是广义圆方树，见OI-wiki；形象的图的话其实可以这么看：先将原图按照tarjan缩点成v-DCC，就长成了蓝书上面的那个图，然后圆方树相当于不让割点单独成点，然后用方点连接一个v-DCC的所有点，割点连接不同的v-DCC；做题步骤还是一样的，但是广义圆方树由于一条边连接的一定是一个圆点和一个方点，更好分类讨论。这道题目具体来说：定义一个环的头是\(\text{dfn}\)最小的点（形象来看，也就是蓝书上面那个缩点之后的图深度最小的割点），方点与头连的边权为\(0\)，与某个剩余点\(x\)连的边权为\(x\)到头的最短距离；询问\(x,y\)的时候，先找到两者在圆方树上的最近公共祖先\(p\)，如果\(p\)是圆点，那么\(x,y\)在原图的最短距离就是圆方树上两者的距离，如果\(p\)是方点，那么\(x,y\)在原图上的路线就会先走到方点所代表的环（也就是一个v-DCC）的两个非头点，然后我们计算这两个非头点的最短距离就好了，具体见下面的代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10,M=2e4+10;
int n,m,q;
int End[2][M<<2],Next[2][M<<2],Last[2][N<<1],Len[2][M<<2],cnt[2];
int dfn[N<<1],visitime,low[N<<1],val[N],dis[N],Dis[N<<1],ringlen[N<<1];
int tot,tp,st[N<<1];
int deep[N<<1];
int f[N<<1][30];
void add(int x,int y,int d,bool op)
{
End[op][++cnt[op]]=y,Next[op][cnt[op]]=Last[op][x],Len[op][cnt[op]]=d,Last[op][x]=cnt[op];
}
void tarjan(int x,int lastedge)
//这里要像找桥边一样判断重边
//因为仙人掌其实是可以有重边的
//比如两个点之间有两条边，仍然不与仙人掌的定义矛盾
{
dfn[x]=low[x]=++visitime;
st[++tp]=x;
for(int i=Last[0][x];i;i=Next[0][i])
{
if((i^1)==lastedge) continue;
int v=End[0][i];
if(!dfn[v])
{
val[v]=Len[0][i];//val是环上最后一条边的权值
dis[v]=dis[x]+Len[0][i];//dis是搜索树上节点到根的距离
tarjan(v,i);
low[x]=min(low[x],low[v]);
if(dfn[x]<=low[v])//此时找到一个v-DCC
{
tot++;//增加一个方点
ringlen[tot]=val[st[tp]]+dis[st[tp]]-dis[x];
//注意此时栈中节点的排列顺序的意义
//从栈顶到x就是这个环的所有点
//而且是按照顺序的
//也就是说环就为st[tp]-st[tp-1]-...-x-st[tp]
//于是可以计算出环的长度
int z;
do
{
z=st[tp--];
int temp=min(ringlen[tot]-(dis[z]-dis[x]),dis[z]-dis[x]);
//点到头的最短距离
add(tot,z,temp,1),add(z,tot,temp,1);
}while(z!=v);
add(x,tot,0,1),add(tot,x,0,1);
//别忘了头和方点之间也要连边
}
}
else if(dfn[v]<dfn[x])
//如果没有自环，可以直接else
//有自环的话，要加上if(dfn[v]<dfn[x])
//此时访问的是一条非树边的返祖边，肯定也就找到了环
//所以要更新val，因为是环的最后一条边
{
low[x]=min(low[x],dfn[v]);
val[x]=Len[0][i];
}
}
}
void deal_first(int u,int father)
{
deep[u]=deep[father]+1;
for(int i=0;i<=15;i++)
f[u][i+1]=f[f[u][i]][i];
for(int i=Last[1][u];i;i=Next[1][i])
{
if(End[1][i]!=father)
{
f[End[1][i]][0]=u;
Dis[End[1][i]]=Dis[u]+Len[1][i];
deal_first(End[1][i],u);
}
}
}
pair<int,int> LCA(int x,int y)//second为-1表示lca为圆点
{
if(x==y) return make_pair(x,-1);//很重要
if(deep[x]<deep[y]) swap(x,y);
for(int i=15;i>=0;i--)
{
if(deep[f[x][i]]>=deep[y])
x=f[x][i];
if(x==y) return make_pair(x,-1);
if(deep[x]==deep[y]) break;
}
for(int i=15;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
if(f[x][0]<=n) return make_pair(f[x][0],-1);
else return make_pair(x,y);//注意返回的是x和y不是两者的父亲
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
tot=n;//tot表示圆方树的节点总个数
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,0),add(v,u,w,0);
//0表示原图的边，1表示圆方树的边
}
tarjan(1,0);//这道题目没有孤立点，所以许多写法都简化了一下
deal_first(1,0);//预处理圆方树的LCA
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
pair<int,int> p=LCA(u,v);
if(p.second==-1) printf("%d\n",Dis[u]+Dis[v]-2*Dis[p.first]);
else
{
int temp=min(ringlen[f[p.first][0]]-abs(dis[p.first]-dis[p.second]),abs(dis[p.first]-dis[p.second]));
printf("%d\n",Dis[u]-Dis[p.first]+Dis[v]-Dis[p.second]+temp);
}
}
return 0;
}