圆方树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Edge{
	int to,nx,val;
}ed[N*2],ed2[N*2];
int h[N],idx;
void add(int a,int b,int c){
	ed[++idx].to=b;
	ed[idx].nx=h[a];
	ed[idx].val=c;
	h[a]=idx;
}
int h2[N],idx2;
void add2(int a,int b,int c){
	ed2[++idx2].to=b;
	ed2[idx2].nx=h2[a];
	ed2[idx2].val=c;
	h2[a]=idx2;
}
int stk[N],tp,dfn[N],low[N],Time,val[N],dis[N],dis2[N],r[N],fang;
void tarjan(int u,int fa){
	stk[++tp]=u;
	dfn[u]=low[u]=++Time;
	for(int i=h[u];i;i=ed[i].nx){
		int v=ed[i].to;
		if(v==fa)continue;
		if(!dfn[v]) {

			val[v]=ed[i].val;
			dis[v]=dis[u]+ed[i].val;//环上到达根节点距离
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){//u是双联通分量根节点
				++fang;//方点
				//此环周长
				r[fang]=val[stk[tp]]+dis[stk[tp]]-dis[u];
				while(1){
					int x=stk[tp--];
					int tmp=dis[x]-dis[u];
					tmp=min(tmp,r[fang]-tmp);//以方点建新图
					add2(x,fang,tmp);add2(fang,x,tmp);
					if(x==v)break;
				}
				add2(u,fang,0);//到达根节点距离是0
				add2(fang,u,0);
			}
		}else if(dfn[v]<dfn[u]){//u->v,双联通分量尽头
			val[u]=ed[i].val;//此点权值，
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int p[N][22],d[N];
void dfs(int u,int fa){//lcac初始化
	for(int i=0;p[u][i];i++)
		p[u][i+1]=p[p[u][i]][i];
	for(int i=h2[u];i;i=ed2[i].nx){
		int v=ed2[i].to;
		if(v==fa)continue;
		dis2[v]=dis2[u]+ed2[i].val;
		p[v][0]=u;
		d[v]=d[u]+1;//深度
		dfs(v,u);
	}
}
int n,m,q;
pair<int,int> lca(int x,int y){
	if(d[x]<d[y])swap(x,y);//x深度大
	for(int dt=d[x]-d[y],i=0;dt;dt>>=1,i++)
		if(dt&1)x=p[x][i];
	if(x==y)return make_pair(x,-1);//圆点,x,y不在一个环里
	for(int i=15;~i;i--)
		if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];
	if(p[x][0]<=n)return make_pair(p[x][0],-1);//圆点
	else return make_pair(x,y);//方点，x与y在一个环里面,分别是找的两个点的祖先
}
int main(){
	cin>>n>>m>>q;
	fang=n;//方点
	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);
	}
	tarjan(1,0);
	dfs(1,0);
	while(q--){
		int u,v;
		scanf("%d%d",&u,&v);
		pair<int,int> pi=lca(u,v);
		if(pi.second==-1)printf("%d\n",dis2[u]+dis2[v]-2*dis2[pi.first]);
		else {//祖先是方点,两个点的祖先直接最小距离需要加上
			int tmp=abs(dis[pi.first]-dis[pi.second]);
			tmp=min(tmp,r[p[pi.first][0]]-tmp);//环上相差的最小距离,
			printf("%d\n",dis2[u]+dis2[v]-dis2[pi.first]-dis2[pi.second]+tmp);
		}
	}
	return 0;
}