90pts求调

#include<bits/stdc++.h>
using namespace std;
int h[100010],nxt[400010],to[400010],e[400010],idx=1;
int hc[10010],nc[400010],tc[400010],ec[400010],ic=0;
int dfn[100010],low[100010],num=0;
int fa[100010],fe[100010],fw[100010],s[100010],siz[100010];
int f[100010][20],dep[100010],d[100010],A,B,n,ccnt;
void add(int a,int b,int c){
    e[++idx]=c;
    to[idx]=b;
    nxt[idx]=h[a];
    h[a]=idx;
}
void add2(int a,int b,int c){
    ec[++ic]=c;
    tc[ic]=b;
    nc[ic]=hc[a];
    hc[a]=ic;
}
void add3(int u,int v,int w){
    int sum=w;
    for(int k=v;k!=u;k=fa[k]){
        s[k]=sum;
        sum+=fw[k];
    }
    add2(u,++ccnt,0);
    for(int k=v;k!=u;k=fa[k]){
        siz[k]=sum;
        add2(ccnt,k,min(s[k],sum-s[k]));
    }
}
void tarjan(int u,int lst){
    dfn[u]=low[u]=++num;
    for(int i=h[u];i;i=nxt[i]){
        int v=to[i],w=e[i];
        if(dfn[v]){
            if(i!=(lst^1))low[u]=min(low[u],dfn[v]);
            continue;
        }
        fa[v]=u;
        fe[v]=i;
        fw[v]=w;
        tarjan(v,i);
        low[u]=min(low[u],low[v]);
        if(dfn[u]<low[v])add2(u,v,w);
    }
    for(int i=h[u];i;i=nxt[i]){
        int v=to[i],w=e[i];
        if(dfn[u]<dfn[v] && fe[v]!=i)add3(u,v,w);
    }
}
void dfs(int x,int fa){
    f[x][0]=fa;
    for(int i=1;i<20;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(int i=hc[x];i;i=nc[i]){
        int y=tc[i];
        if(y==fa)continue;
        d[y]=d[x]+ec[i];
        dep[y]=dep[x]+1;
        dfs(y,x);
    }
}
int lca(int x,int y){
    if(dep[x]>dep[y])swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[f[y][i]]>=dep[x])y=f[y][i];
    }
    if(x==y)return x;
    for(int i=19;i>=0;i--){
        if(f[y][i]!=f[x][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    A=x;
    B=y;
    return f[x][0];
}
int query(int x,int y){
    int p=lca(x,y);
    if(p<=n)return d[x]+d[y]-2*d[p];
    int l=abs(s[A]-s[B]);
    int dAB=min(l,siz[A]-l);
    return dAB+d[x]+d[y]-d[A]-d[B];
}
int main(){
    int m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    ccnt=n;
    tarjan(1,-1);
    dep[1]=1;
    dfs(1,0);
    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",query(u,v));
    }
    return 0;
}