静态仙人掌
仙人掌定义：对一个无向连通图，任意一条边属于至多一个简单环。
思路
每个询问是两点之间的最短路，我们求最短路一般都是在树型结构上，而仙人掌图会存在环，但是每条边最多在一个环中，所以环不会互相影响，我们要对这些环做一些处理。
我们把每个环重新建为方点，而原来图上的点叫做原点。（圆方树的思想）。这样就可以直接做最短路了。
找环，建方点
一点个人理解：环变成的方点并不是真的变成了一个点，而是将整个环封装成一个点。每回访问的时候，只访问其中两个点的最短距离，所以可以预处理出来整个环的长度，和环上每个点到某个点的长度。最短距离就可以直接求出来（后面会有说明）。
找环，缩点。可以用 tarjan 实现。
void t_j(int k,int f){//缩点，连边
l_w[k]=d_f[k]=++x_x;//时间戳
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
q_q[v].f=k;
q_q[v].v=p_p[i].l;
t_j(v,k);
l_w[k]=min(l_w[v],l_w[k]);
}else if(v!=f)l_w[k]=min(l_w[k],d_f[v]);
if(l_w[v]>d_f[k]){//处理环外的点的连边
a_dd(v,k,p_p[i].l);
a_dd(k,v,p_p[i].l);
}
}
for(int i=h_d[k];i;i=p_p[i].n_t){//处理环上的点的连边
int v=p_p[i].v;
if(q_q[v].f==k||d_f[v]<=d_f[k])continue;
a_t(k,v,p_p[i].l);//“封装”的方点
}
}缩点的时候同时将原来的边在新图上连出来。注意环上的点之间的连边特殊处理（就是建方点）。
void a_t(int u,int v,int l){//处理环，连方节点到环的每个点
n_p++;
int l_l=l,i=v;
while(i!=q_q[u].f){//存整个环的大小
q_q[i].s_m=l_l;//到先遍历的点的距离
l_l+=q_q[i].v;
i=q_q[i].f;//因为是个环，所以找父节点找到最后就是最开始的那个点
}
q_q[n_p+n].s_m=q_q[u].s_m;//赋方节点初值
i=v;
q_q[u].s_m=0;
int n_x;
while(i!=q_q[u].f){
n_x=min(q_q[i].s_m,q_q[n_p+n].s_m-q_q[i].s_m);//环两边走法，那个近存那个
a_dd(n_p+n,i,n_x);//方节点和其它点连边
a_dd(i,n_p+n,n_x);
i=q_q[i].f;
}
}公共祖先LCA
这里可以用倍增和树链剖分两种算法，倍增会更快，但是树链剖分处理更方便。所以这里使用树链剖分解法。（建图虽然有些麻烦，但是处理会非常方便，也更加灵活）
struct pp{//存点
int f;//父节点
int t_p;//链顶
int v;//边转点的价值
int s_m;//在环中和最先遍历的点的距离（时间戳最小的点）
int s_z;//子树和它的重量
int d_p;//深度
int b_s;//重儿子
int l_g;//到根节点的距离
}q_q[o_o<<1];注意要多存一个每个节点到根节点的距离。方便算最短路的距离。
最短路
先找两个点的公共祖先。
如果在原点上直接输出两个点分别到根节点的距离减去两倍的公共祖先到根节点的距离即可。
否则，找到两个点分别到“封装”的方点最近的点（就是两个点最短进入环的那两个点）。将两个点的路长度先记上，再加上“封装”好的环中直接计算得到的最短长度。
int g_m(int a,int b,int g_f){
if(g_f<=n)return (q_q[a].l_g+q_q[b].l_g-2*q_q[g_f].l_g);//若公共祖先在圆点上，直接用两点到跟的距离减公共祖先到根的距离的两倍即可
int h_a=f_h(a,g_f),h_b=f_h(b,g_f); //找到入环的点
int a_s=q_q[a].l_g-q_q[h_a].l_g+q_q[b].l_g-q_q[h_b].l_g;//先记上两点到环的距离
if(q_q[h_a].s_m<q_q[h_b].s_m)swap(h_a,h_b);
a_s+=min(q_q[h_a].s_m-q_q[h_b].s_m,q_q[g_f].s_m-q_q[h_a].s_m+q_q[h_b].s_m);//环上两条路，两点最小距离
return a_s;
}“封装”的方点本身其实是一个已经处理好的环，但是在图上可以看做点来遍历。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<cctype>
#include<stack>
#include<bitset>
#include<map>
#include<utility>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e6+10;
struct po{//存边
int v;
int l;
int n_t;
}p_p[o_o],p_pp[o_o];
int h_d[o_o],h_dd[o_o],x_p,x_pp;
int n,m,q;
void a_d(int u,int v,int l){//原图边
p_p[++x_p].v=v;
p_p[x_p].l=l;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
int l_w[o_o],d_f[o_o],x_x;//tarjan的时间戳和最小能到达时间的戳标记
struct pp{//存点
int f;//父节点
int t_p;//链顶
int v;//边转点的价值
int s_m;//在环中和最先遍历的点的距离（时间戳最小的点）
int s_z;//子树和它的重量
int d_p;//深度
int b_s;//重儿子
int l_g;//到根节点的距离
}q_q[o_o<<1];
int n_p;//方节点编号
void a_dd(int u,int v,int l){//新图边
p_pp[++x_pp].v=v;
p_pp[x_pp].l=l;
p_pp[x_pp].n_t=h_dd[u];
h_dd[u]=x_pp;
}
void a_t(int u,int v,int l){//处理环，连方节点到环的每个点
n_p++;
int l_l=l,i=v;
while(i!=q_q[u].f){//存整个环的大小
q_q[i].s_m=l_l;//到先遍历的点的距离
l_l+=q_q[i].v;
i=q_q[i].f;
}
q_q[n_p+n].s_m=q_q[u].s_m;//赋方节点初值
i=v;
q_q[u].s_m=0;
int n_x;
while(i!=q_q[u].f){
n_x=min(q_q[i].s_m,q_q[n_p+n].s_m-q_q[i].s_m);//环两边走法，那个近存那个
a_dd(n_p+n,i,n_x);//方节点和其它点连边
a_dd(i,n_p+n,n_x);
i=q_q[i].f;
}
}
void t_j(int k,int f){
l_w[k]=d_f[k]=++x_x;
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
q_q[v].f=k;
q_q[v].v=p_p[i].l;
t_j(v,k);
l_w[k]=min(l_w[v],l_w[k]);
}else if(v!=f)l_w[k]=min(l_w[k],d_f[v]);
if(l_w[v]>d_f[k]){//处理环外的点
a_dd(v,k,p_p[i].l);
a_dd(k,v,p_p[i].l);
}
}
for(int i=h_d[k];i;i=p_p[i].n_t){//处理环上的点
int v=p_p[i].v;
if(q_q[v].f==k||d_f[v]<=d_f[k])continue;
a_t(k,v,p_p[i].l);
}
}
void d_1(int k,int f){
q_q[k].f=f;
q_q[k].s_z=1;
for(int i=h_dd[k];i;i=p_pp[i].n_t){
int v=p_pp[i].v;
if(v==f)continue;
q_q[v].d_p=q_q[k].d_p+1;
q_q[v].l_g=q_q[k].l_g+p_pp[i].l;
d_1(v,k);
q_q[k].s_z+=q_q[v].s_z;
if(q_q[v].s_z>q_q[q_q[k].b_s].s_z)q_q[k].b_s=v;
}
}
void d_2(int k,int t_p){
q_q[k].t_p=t_p;
if(q_q[k].b_s)d_2(q_q[k].b_s,t_p);
for(int i=h_dd[k];i;i=p_pp[i].n_t){
int v=p_pp[i].v;
if(v==q_q[k].f||v==q_q[k].b_s)continue;
d_2(v,v);
}
}
int g_f(int a,int b){//找公共祖先
while(q_q[a].t_p!=q_q[b].t_p){
if(q_q[q_q[a].t_p].d_p<q_q[q_q[b].t_p].d_p)swap(a,b);
a=q_q[q_q[a].t_p].f;
}
if(q_q[a].d_p>q_q[b].d_p)swap(a,b);
return a;
}
int f_h(int a,int f){
int a_s;
while(q_q[a].t_p!=q_q[f].t_p){//点进入公共祖先的链
a_s=q_q[a].t_p;
a=q_q[q_q[a].t_p].f;
}
if(a==f)return a_s;//如果这条链的链顶的父亲是公共祖先链的链顶，那返回这个点
else return q_q[f].b_s;//否则返回共公祖先的重儿子节点
}
int g_m(int a,int b,int g_f){
if(g_f<=n)return (q_q[a].l_g+q_q[b].l_g-2*q_q[g_f].l_g);//若公共祖先在圆点上，直接用两点到跟的距离减公共祖先到根的距离的两倍即可
int h_a=f_h(a,g_f),h_b=f_h(b,g_f); //找到入环的点
int a_s=q_q[a].l_g-q_q[h_a].l_g+q_q[b].l_g-q_q[h_b].l_g;//先记上两点到环的距离
if(q_q[h_a].s_m<q_q[h_b].s_m)swap(h_a,h_b);
a_s+=min(q_q[h_a].s_m-q_q[h_b].s_m,q_q[g_f].s_m-q_q[h_a].s_m+q_q[h_b].s_m);//环上两条路，两点最小距离
return a_s;
}
int main(){
n=r_r(),m=r_r(),q=r_r();
for(int i=1;i<=m;i++){
int a=r_r(),b=r_r(),l=r_r();
a_d(a,b,l);
a_d(b,a,l);
}
t_j(1,0);//处理环，建新图
//树链剖分
d_1(1,0);
d_2(1,1);
for(int i=1;i<=q;i++){
int a=r_r(),b=r_r();
int a_b=g_f(a,b);
printf("%d\n",g_m(a,b,a_b));
}
return 0;
}
