记录编号	394176	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	WildRage	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2017-04-13 08:41:02	内存使用	3.86 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct edge{
	int START,END,w,next;
	bool operator < (const edge &a)const{
		return w>a.w;
	}
}v[100005],r[100005];
struct Op{
	int S,E,ans;
}op[30005];
int T[10005],dis[10005],father[10005];
int first[10005],p=1;
int find(int a){
	if(father[a]!=a)father[a]=find(father[a]);
	return father[a];
}
void add(int a,int b,int c){
	v[p].END=b;
	v[p].w=c;
	v[p].next=first[a];
	first[a]=p++;
}
void spfa(int x){
	memset(dis,-1,sizeof(dis));
	dis[x]=0x7fffffff;
	int flag[10005]={0};
	queue<int> Q;
	Q.push(x);
	while(!Q.empty()){
		int k=Q.front();
		for(int i=first[k];i!=-1;i=v[i].next){
			if(dis[v[i].END]<min(dis[k],v[i].w)){
				dis[v[i].END]=min(dis[k],v[i].w);
				if(!flag[v[i].END]){
					flag[v[i].END]=1;
					Q.push(v[i].END);
				}
			}
		}
		Q.pop();flag[k]=0;
	}
}
int main()
{
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    memset(first,-1,sizeof(first));
	int n,m,a,b,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		r[p].START=a;
		r[p].END=b;
		r[p].w=c;
		p++;
		r[p].START=b;
		r[p].END=a;
		r[p].w=c;
		p++;
	}
	int P;
	scanf("%d",&P);
	for(int i=1;i<=P;i++){
		scanf("%d%d",&op[i].S,&op[i].E);
		T[op[i].S]++;
		T[op[i].E]++;
	}
	sort(r+1,r+p);
	for(int i=1;i<=n;i++)father[i]=i;
	int k=0;
	int K=p;
	p=1;
	for(int i=1;i<K;i++){
		int x=r[i].START;
		int y=r[i].END;
		if(find(x)!=find(y)){
			father[find(y)]=find(x);
			add(x,y,r[i].w);
			add(y,x,r[i].w);
			k++;
		}
		if(k==n-1)break;
	}
	for(int i=1;i<=n;i++){
		if(T[i]>0){
			spfa(i);
			for(int j=1;j<=P;j++){
				if(op[j].ans==0){
					if(op[j].S==i){
						op[j].ans=dis[op[j].E];
						T[op[j].S]--;
						T[op[j].E]--;
					}else if(op[j].E==i){
						op[j].ans=dis[op[j].S];
						T[op[j].S]--;
						T[op[j].E]--;
					}
				}
			}
		}
	}
	for(int i=1;i<=P;i++){
		printf("%d\n",op[i].ans);
	}
	//while(1);
}