题意

给你一颗仙人掌，每一次问两点间的路径

题解

很少做仙人掌的题啊
我们一个方法，把仙人掌变为树
我们依然定义，1为根
我们考虑每一个环，我们找他最接近1的节点为父亲，成为顶，别的所有节点都连向他
我们就可以得到一棵树了
我们队图，由1出发，SPFA一下，可以得到原图1到每一个节点的距离f，显然地，两个点x，y，你只要找到他的LCA或者LCA所在的环
如果相遇的地方恰好是一个点，不是环，那么$f[x]+f[y]-2*f[LCA]$就是答案了
否则，我们找到树上相遇之前的两个点$x'$，$y'$
这个点就是他们第一次跳到这个环的点
代价依然是$f[x]-f[x']$和$f[y]-f[y']$
环上怎么走就要讨论了
我们预处理一下这个点，他到顶的两个距离，分别是往左走或者往右走
那么环上两个点的最短距离就是$min(abs(r[x]-r[y]),min(l[x]+r[y],l[y]+r[x]))$
这个自己画下图就好了
然后就可以了
至于顶，他可能属于多个不同的块这都不用管
因为每个点如果在环里面，最多当一个环的非顶点
就保存哪一个就可以了
因为你在讨论的时候，你倍增的LCA是顶点，退下来肯定是两个非顶点

然后至于怎么找环，因为这是一个仙人掌，所以我就用了一个很暴力的方法
直接建立dfs树，如果出现返祖边，就把这个环所有点拿出来，暴力搞
因为每一条边最多属于一个环所以不影响复杂度

最后要注意的是，如果两个点在同一个环里面，不要标记这个环的环顶，要标记这个点和他父亲的连边属于哪一个环，因为环顶可能会重复

然后就可以解决这题了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=10005;
const int M=12000;
int n,m,Q;
struct qq
{int x,y,z,last;
}e[M*2];int num,last[N];
void init (int x,int y,int z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
int f[N];
bool vis[N];
queue<int> q;
void SPFA ()
{memset(vis,false,sizeof(vis));memset(f,127,sizeof(f));q.push(1);f[1]=0;vis[1]=true;while (!q.empty()){int x=q.front();q.pop();vis[x]=false;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (f[y]>f[x]+e[u].z){f[y]=f[x]+e[u].z;if (vis[y]==false){vis[y]=true;q.push(y);}}}}
}
int dfn[N],id;//胡乱建树 
int o[N];//与父亲连边的权值 
int fa[N][20];//dfs树上的父亲
int h[N];
int l[N],r[N];
int cnt;//环的编号
int belong[N]; 
void dispose (int top,int x,int z)//出现了一个环 最顶端是top 返祖边的权值 
{cnt++;int now=x,sum=z;while (now!=top){l[now]=sum;sum=sum+o[now]; belong[now]=cnt;now=fa[now][0];}l[now]=sum;now=x;while (now!=top){r[now]=sum-l[now];int ff=fa[now][0];fa[now][0]=top;now=ff;}
}
void dfs (int x)
{dfn[x]=++id;belong[x]=x;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (h[x]==y) continue;if (dfn[y]==-1) {o[y]=e[u].z;h[y]=fa[y][0]=x;dfs(y);}else    if (dfn[y]<=dfn[x]) dispose(y,x,e[u].z);}
}
int dep[N];
int solve (int x,int y)
{int xx=x,yy=y;if (dep[x]<dep[y]) swap(x,y);for (int u=18;u>=0;u--){if (dep[fa[x][u]]>=dep[y]){x=fa[x][u];}}for (int u=18;u>=0;u--)if (fa[x][u]!=fa[y][u]){x=fa[x][u];y=fa[y][u];}if (belong[x]==belong[y])//如果在一个环上面{int ans=f[xx]-f[x]+f[yy]-f[y];ans=ans+min(abs(r[x]-r[y]),min(l[x]+r[y],l[y]+r[x]));return ans;}else{x=fa[x][0];return f[xx]+f[yy]-2*f[x];}
}
void dfs2 (int x)//深度处理一下 
{for (int u=1;u<=18;u++) fa[x][u]=fa[fa[x][u-1]][u-1];for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;dep[y]=dep[x]+1;dfs2(y);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d%d",&n,&m,&Q);cnt=n;for (int u=1;u<=m;u++){int x,y,z;scanf("%d%d%d",&x,&y,&z);init(x,y,z);init(y,x,z);}SPFA();memset(dfn,-1,sizeof(dfn));dfs(1);num=0;memset(last,-1,sizeof(last));for (int u=2;u<=n;u++)  init(fa[u][0],u,0);dep[1]=1;dfs2(1);while (Q--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",solve(x,y));}return 0;
}