cogs1439 货车运输

---

一道傻逼板子题。

边一定在最大生成树上，这个可以用消圈证明

然后kruskal跑一遍再搜一遍再建ST表再跑LCA这题就做完了。

RT

PS.交上去的代码把Kruskal打成了Kruscal(=v=)

COGS上莫名RE两个小点，别的OJ都能AC（今天竟然一次AC了，我的欧！）

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cmath>

#define Fname "truck"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

il int gi(){

    rg int x=0;rg bool flg=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return flg?-x:x;

}

const int maxn=10010,maxm=50010;

int n,m;

int fa[maxn];

int fir[maxn],dis[maxn<<1],id,nxt[maxn<<1],w[maxn<<1];

il vd add(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}

il int hd(int i){return fa[i]==i?i:fa[i]=hd(fa[i]);}

namespace Kruscal{

	struct edge{int a,b,c;};

	il bool cmp(edge a,edge b){return a.c>b.c;}

	edge e[maxm];

	il vd main(){

		rep(i,1,m)e[i].a=gi(),e[i].b=gi(),e[i].c=gi();

		int now=1;

		sort(e+1,e+m+1,cmp);

		rep(i,1,n)fa[i]=i;

		rep(i,2,n){

			while(now<=m&&hd(e[now].a)==hd(e[now].b))++now;

			if(now>m)return;

			fa[hd(e[now].a)]=hd(e[now].b),add(e[now].a,e[now].b,e[now].c),add(e[now].b,e[now].a,e[now].c);

		}

	}

}

int st[maxn][14],Min[maxn][14],dep[maxn];

il vd dfs(int x){erep(i,x)if(st[x][0]^dis[i])st[dis[i]][0]=x,dep[dis[i]]=dep[x]+1,Min[dis[i]][0]=w[i],dfs(dis[i]);}

int main(){

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

	n=gi(),m=gi();int Log=log2(n);

	Kruscal::main();

	rep(i,1,n)if(!st[i][0])st[i][0]=-1,dep[i]=1,dfs(i);

	rep(i,1,Log)rep(j,1,n)st[j][i]=st[st[j][i-1]][i-1],Min[j][i]=min(Min[j][i-1],Min[st[j][i-1]][i-1]);

	int q=gi();

	while(q--){

		static int x,y;x=gi(),y=gi();

		if(hd(x)^hd(y)){puts("-1");continue;}

		static int ans,cha;ans=2147483647;

		cha=dep[x]-dep[y];

		if(cha<0)swap(x,y),cha=-cha;

		rep(i,0,Log)if(cha&(1<<i))ans=min(ans,Min[x][i]),x=st[x][i];

		if(x^y)drep(i,Log,0)if(st[x][i]^st[y][i])ans=min(ans,min(Min[x][i],Min[y][i])),x=st[x][i],y=st[y][i];

		if(x^y)ans=min(ans,min(Min[x][0],Min[y][0]));

		printf("%d\n",ans);

	}

	return 0;

}