记录编号	442740	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]最短路(杨天)	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.693 s
提交时间	2017-08-28 13:52:58	内存使用	61.35 MiB

//要求环的prefer child一直和方点相连
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
void stop(){
	
}
const int N=2e6+10;
int n,m,q,id,son[N][2],fa[N],cir[N][2],len[N],sum[N];
bool ise[N],square[N],rev[N],iscir[N];
bool isroot(int x){
	return x!=son[fa[x]][0]&&x!=son[fa[x]][1];
}
#define lc son[x][0]
#define rc son[x][1]
void print(int x){
	if (!x) return;
	print(lc);
	printf("%d ",x);
	print(rc);
}
void update(int x){
	iscir[x]=square[x];
	sum[x]=len[x];
	if (lc) sum[x]+=sum[lc],iscir[x]|=iscir[lc];
	if (rc) sum[x]+=sum[rc],iscir[x]|=iscir[rc];
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;
	if (y==son[z][1]) son[z][1]=x;
	if (y==cir[z][0]) cir[z][0]=x;
	if (y==cir[z][1]) cir[z][1]=x;
	update(y);update(x);
}
void flip(int x){
	if (!x) return;
	swap(lc,rc);rev[x]^=1;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		flip(lc);flip(rc);
		if (square[x]) swap(cir[x][0],cir[x][1]);
		rev[x]=0;
	}
}
void splay(int x){
	pushdown(x);
	for (;!isroot(x);rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!isroot(y)) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
void reset(int z,int x){//把z的prefer child改成x
	splay(x);
	len[z]=min(sum[lc],sum[rc]);//最短路嘛...
	fa[cir[z][0]=lc]=z;
	fa[cir[z][1]=rc]=z;
	lc=rc=0;
	update(x);
	fa[son[z][1]=x]=z;
	update(z);
}
void access(int x){
	int p=x;
	for (int y=0;x;y=x,x=fa[x]){
		splay(x);
		int z=fa[x];
		if (square[z]){//x是环点,且要更换prefer child
			//下传标记
			splay(z);
			//重新连上整个环
			int cp=son[z][1];
			son[z][1]=0;
			update(z);
			for (pushdown(cp);son[cp][0];pushdown(cp=son[cp][0]));
			splay(cp);
			fa[son[cp][0]=cir[z][0]]=cp;
			fa[son[cp][1]=cir[z][1]]=cp;
			cir[z][0]=cir[z][1]=0;
			update(cp);
			//把prefer child改成x
			reset(z,x);
		}
		rc=y;
		update(x);
	}
	splay(p);
}
void makeroot(int x){
	access(x);flip(x);
}
int getroot(int x){
	int y=x;
	while (fa[y]) y=fa[y];
	access(x);
	return y;
}
int newnode(int l,bool tp){
	int x=++id;
	ise[x]=1;
	square[x]=tp;
	len[x]=sum[x]=l;
	return x;
}
/*map<pair<pair<int,int>,int>,int> M;
#define mp make_pair*/
bool link(int x,int y,int l){
	if (x==y) return 0;
	makeroot(x);
	if (getroot(y)==x){
		if (iscir[y]) return 0;//已经有环了...
		//要成环,把环的prefer child设为y
		fa[son[y][1]=newnode(l,0)]=y;
		update(y);
		splay(x);
		//print(x);puts("");
		fa[rc]=0;rc=0;
		update(x);
		fa[++id]=x;square[id]=1;
		reset(id,y);
	}
	else fa[fa[x]=newnode(l,0)]=y;//树上情况
	//M[mp(mp(x,y),l)]++;
	return 1;
}
/*bool cut(int x,int y,int l){
	if (!M[mp(mp(x,y),l)]) return 0;
	M[mp(mp(x,y),l)]--;
	makeroot(y);
	access(x);
	if (iscir[x]){//删掉了一条环上的边
		
	}
	else{//树上情况
		root[lc]=1;
		fa[lc]=0;lc=0;
		update(x);
	}
	return 1;
}*/
int dis(int x,int y){
	makeroot(x);
	return getroot(y)!=x?-1:sum[y];
}
int main()
{
	//freopen("a.txt","r",stdin);
	freopen("nt2011_path.in","r",stdin);
	freopen("nt2011_path.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);id=n;
	int x,y,l;
	for (int i=1;i<=m;i++){
		x=read();y=read();l=read();
		//printf("link %d\n",i);
		if (i==21) stop();
		if (link(x,y,l)) ;//printf("%d %d\n",x,y);
		/*printf("link(%d,%d,%d)\n",x,y,l);
		if (i==14) stop();
		puts(link(x,y,l)?"ok":"failed");*/
	}
	for (int i=1;i<=q;i++){
		x=read();y=read();
		//printf("query(%d,%d) id=%d\n",x,y,i);
		printf("%d\n",dis(x,y));
	}
	return 0;
}