【题意】给定带边权仙人掌图，Q次询问两点间最短距离。n,m,Q<=10000

【算法】圆方树处理仙人掌问题

【题解】树上的两点间最短路问题，常用倍增求LCA解决，考虑扩展到仙人掌图。

先对仙人掌图建圆方树，圆圆边和原图边权一致。对于每个方点代表的环，记深度最小的点为x，则圆方边的边权是圆点到x的最短距离。

若lca(u,v)为圆点，则两点间最短路转化为圆方树上dis[u]+dis[v]-2*dis[lca]。（向上延伸的路径，经过环则必然经过每个方点的x，计算无误）

若lca(u,v)为方点，则记u,v在方点连接的圆点A,B的子树内，那么两点间最短路为dis[u]+dis[v]-dis[A]-dis[B]+dis(A,B)，dis(A,B)是A,B在环上的短侧路径。

复杂度O(Q log n)。

实现细节：

1.Tarjan：建圆方树（先处理树边，最后在深度最小处处理环）

2.处理方点：s[i]表示点i从所在环点x（深度最小）开始逆时针的距离，最终s[x]记为s[N]后s[x]=0。另外注意要记录一下环中点的编号顺序。

3.LCA：圆点直接计算，方点中dis(A,B)=min{ s[A]+s[w]-s[B] , s[B]-s[A] }（A在B的顺时针方向，否则交换AB）。

4.注意防止访问父亲的边是i^1，初始tot=1。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=20010;int N,fa[maxn],b[maxn],f[maxn][20],dfn[maxn],low[maxn],dfsnum=0,deep[maxn],A,B,n,m,id[maxn];ll s[maxn],dis[maxn];struct tu{    int first[maxn],tot;    struct edge{
    int v,w,from;}e[maxn*2];    void insert(int u,int v,int w){        tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;        tot++;e[tot].v=u;e[tot].w=w;e[tot].from=first[v];first[v]=tot;    }}G;int first[maxn],tot;struct edge{
    int v,w,from;}e[maxn*2];void insert(int u,int v,int w){    tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;    tot++;e[tot].v=u;e[tot].w=w;e[tot].from=first[v];first[v]=tot;}void solve(int u,int v,int w){    N++;    int pre=w,ID=0;    for(int i=v;i!=fa[u];i=fa[i]){        s[i]=pre;        pre+=b[i];        id[i]=ID++;    }    s[N]=s[u];s[u]=0;    for(int i=v;i!=fa[u];i=fa[i])insert(N,i,min(s[i],s[N]-s[i]));}void tarjan(int x,int father){    dfn[x]=low[x]=++dfsnum;    for(int i=G.first[x];i;i=G.e[i].from)if(i!=father){        int y=G.e[i].v;        if(!dfn[y]){            fa[y]=x;b[y]=G.e[i].w;            tarjan(G.e[i].v,i^1);            low[x]=min(low[x],low[y]);        }else low[x]=min(low[x],dfn[y]);        if(low[y]>dfn[x])insert(x,y,G.e[i].w);    }    for(int i=G.first[x];i;i=G.e[i].from){        int y=G.e[i].v;        if(fa[y]!=x&&dfn[y]>dfn[x])solve(x,y,G.e[i].w);    }}void dfs(int x,int father){    for(int j=1;(1<
         
          <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];    for(int i=first[x];i;i=e[i].from)if(i!=father){        f[e[i].v][0]=x;        deep[e[i].v]=deep[x]+1;        dis[e[i].v]=dis[x]+e[i].w;        dfs(e[i].v,i^1);    }}int lca(int x,int y){    if(deep[x]
          
           =0;i--)if((1<
           
            <=deep[x]&&f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } A=x;B=y; return f[x][0];}int main(){ int Q; scanf("%d%d%d",&n,&m,&Q); int u,v,w; G.tot=1;tot=1; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); G.insert(u,v,w); } N=n;tarjan(1,0);dfs(1,0); while(Q--){ scanf("%d%d",&u,&v); w=lca(u,v); if(w<=n)printf("%lld\n",dis[u]+dis[v]-2*dis[w]); else{ ll ans=dis[u]+dis[v]-dis[A]-dis[B]; if(id[A]