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;
}