分类： 洛谷题库

按照我们之前的经验，仙人掌上问题往往可以通过圆方树转化为树上问题。
我们发现，最短路在树上是一种非常容易解决的问题。只需预处理到根节点的长度然后死命跑LCA就可以了。
但是在一般图上，最短路的实时处理就会变得很困难。
我们可以尝试通过给圆方树上的边赋上特别的边权来处理这个问题。

对于圆-圆边，赋边权为原边权，这是容易理解的。
对于方点到它的父亲圆点的边，赋边权为0，对于圆点到它的父亲方点的边，赋边权为这个圆点到这个方点的父亲圆点的最短距离。

这时候我们会遇到一个问题，就是Tarjan找环的时候找不到返祖边的边权。
解决方案是记录每一个到根节点在dfs树上的距离，然后当我们找到一个环一路找爸爸并统计长度即可。

然后是计算答案，我们发现，如果询问的两个点的最近公共祖先是一个方点，那么它们的答案不能用普通方法计算。
我一开始的想法是尝试直接用某个节点到父亲方点的边权直接计算答案，但这样会导致答案错误，原因是它无法正确地区分两个点位于圆环的同一侧还是不同侧的情况。
故而，我们需要保存原来的距离它的父亲方点的靠某一侧的距离，故而当lca是方点的时候特殊判断计算即可。

 #include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

typedef long long ll;

inline ll Min(ll A,ll B){
    return A<B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline ll Abs(ll A){
	return A>0?A:-A;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}

struct ee{
    int v;
    ll w;
    int nxt;
}e[200005];
int h0[10005],h[20005],et=0;
inline void Eadd(int *H,int U,int V,ll W){
    e[++et]=(ee){V,W,H[U]};
    H[U]=et;
}
inline void add(int *H,int U,int V,ll W){
    Eadd(H,U,V,W);
    Eadd(H,V,U,W);
}
int dfn[20005],lw[20005],cnt=0,dep[20005],fa[20005][30];
ll dis[20005],sz[20005];
int nm=0;
int st[20005],tp=0;
inline void dfs0(int X){
    dfn[X]=lw[X]=++cnt;
    Fv(h0,i,X){
    	if(e[i].v==fa[X][0]){
    		continue;
		}
        if(!dfn[e[i].v]){
            fa[e[i].v][0]=X;
            dis[e[i].v]=dis[X]+e[i].w;
            dfs0(e[i].v);
            lw[X]=Min(lw[X],lw[e[i].v]);
    	}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
			if(e[i].v!=fa[X][0]&&dfn[e[i].v]<dfn[X]){
                ++nm;
                add(h,nm,e[i].v,0);
                ll len=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                	len+=dis[j]-dis[fa[j][0]];
                }
                sz[nm]=len;
                ll nw=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                    add(h,nm,j,Min(nw,len-nw));
                    sz[j]=nw; 
                    nw+=dis[j]-dis[fa[j][0]];
                }
            }
        }
        if(lw[e[i].v]>dfn[X]){
        	add(h,X,e[i].v,e[i].w);
		} 
    }
}

inline void dfs1(int X,int FA){
    dep[X]=dep[FA]+1;
    fa[X][0]=FA;
    Fv(h,i,X){
        if(e[i].v!=FA){
            dis[e[i].v]=dis[X]+e[i].w;
            dfs1(e[i].v,X);
        }
    }
}

int n,m,q;

inline ll calc(int X,int Y){
    int XX=X,YY=Y,lca;
    while(dep[XX]<dep[YY]){
        Swap(XX,YY);
    }
    for(int i=20;~i;--i){
        if(dep[XX]-(1<<i)>=dep[YY]){
            XX=fa[XX][i];
        }
    }
    if(XX==YY){
        lca=XX;
    }else{
        for(int i=20;~i;--i){
            if(fa[XX][i]!=fa[YY][i]){
                XX=fa[XX][i];
                YY=fa[YY][i];
            }
        }
        lca=fa[XX][0];
    }
    ll RT=dis[X]+dis[Y]-(dis[lca]<<1);
    if(lca>n){
        ll P=dis[XX]-dis[lca],Q=dis[YY]-dis[lca];
        RT-=(P+Q);
        RT+=Min(sz[lca]-Abs(sz[XX]-sz[YY]),Abs(sz[XX]-sz[YY]));
    }
    return RT;
}



void init(){
    scanf("%d%d%d",&n,&m,&q);
    nm=n;
    int u,v;
	ll w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%lld",&u,&v,&w);
        add(h0,u,v,w);
    }
    fa[1][0]=0;
    dfs0(1);
    for(int i=1;i<=nm;++i){
        dep[i]=0,dis[i]=0;
    }
    dfs1(1,0);
    for(int j=1;j<=20;++j){
        for(int i=1;i<=nm;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    int x,y;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&x,&y);
        printf("%lld\n",calc(x,y));
    }
}
int main(){
    init();
    return 0;
}