记录编号	328291	评测结果	AAAAAAAAAA
题目名称	[郑州培训2012] 暴力摩托	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2016-10-23 21:26:55	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210,maxe=1010;
struct edge1{
	int from,to,w;
	bool operator<(const edge1 &e)const{return w<e.w;}
}ee[maxe];
struct edge{int to,w,prev;}e[maxe<<1];
int findroot(int);
void mergeset(int,int);
void addedge(int,int,int);
void deledge(int,int);
void dfs(int);
int n,m,k,last[maxn],len=0,prt[maxn],cnt=0,p[maxn],u[maxn],v[maxn],ans[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("motor.in","r",stdin);
	freopen("motor.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	memset(ans,63,sizeof(ans));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)prt[i]=i;
	for(int i=1;i<=m;i++)scanf("%d%d%d",&ee[i].from,&ee[i].to,&ee[i].w);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)scanf("%d%d",&u[i],&v[i]);
	sort(ee+1,ee+m+1);
	for(int i=1;i<=m;i++){
		if(findroot(ee[i].from)==findroot(ee[i].to)){
			memset(p,-1,sizeof(p));
			dfs(ee[i].from);
			int j=p[ee[i].to];
			for(int x=e[p[ee[i].to]].to;x!=ee[i].from;x=e[p[x]].to)if(e[p[x]].w<e[j].w)j=p[x];
			deledge(e[j].to,j^1);
			deledge(e[j^1].to,j);
		}
		else{
			cnt++;
			mergeset(ee[i].from,ee[i].to);
		}
		addedge(ee[i].from,ee[i].to,ee[i].w);
		addedge(ee[i].to,ee[i].from,ee[i].w);
		for(int i=1;i<=k;i++){
			memset(p,-1,sizeof(p));
			dfs(v[i]);
			int mx=1<<31,mn=~mx;
			int x=u[i];
			for(;p[x]!=-1&&x!=v[i];x=e[p[x]].to){
				mn=min(mn,e[p[x]].w);
				mx=max(mx,e[p[x]].w);
			}
			if(x==v[i])ans[i]=min(ans[i],mx-mn);
		}
	}
	for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
int findroot(int x){return prt[x]==x?x:(prt[x]=findroot(prt[x]));}
void mergeset(int x,int y){prt[findroot(x)]=findroot(y);}
void addedge(int x,int y,int z){
	e[len].to=y;
	e[len].w=z;
	e[len].prev=last[x];
	last[x]=len++;
}
void deledge(int x,int i){
	if(last[x]==i)last[x]=e[i].prev;
	else for(int j=last[x];j!=-1;j=e[j].prev)if(e[j].prev==i){
		e[j].prev=e[i].prev;
		break;
	}
}
void dfs(int x){
	for(int i=last[x];i!=-1;i=e[i].prev)if(p[x]==-1||e[i].to!=e[p[x]].to){
		p[e[i].to]=i^1;
		dfs(e[i].to);
	}
}