2281.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<algorithm>
using namespace std;
struct line
{
	int b,e,len;
};
line li[1000005];
int u[100005];
int n,m;
bool cmp(line a,line b)
{
	if(a.len < b.len)return true;
	else return false;
}
int findhead(int x)
{
	if(u[x]==x)return x;
	else
	{
		u[x]=findhead(u[x]);
		return u[x];
	}
}

int main()
{
	int i,j,k;
	int x,y;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<m;i++)
			scanf("%d%d%d",&li[i].b,&li[i].e,&li[i].len);
		sort(&li[0],&li[m],cmp);
		
		scanf("%d%d",&x,&y);
		for(i=1;i<=n;i++)u[i]=i;
		int ha,hb;
		for(i=m-1;i>=0;i--)
		{
			ha=findhead(li[i].b);
			hb=findhead(li[i].e);
			if(ha!=hb)u[hb]=ha;
			ha=findhead(x);
			hb=findhead(y);
			if(ha==hb)break;
		}
		printf("%d\n",li[i].len);
			



	}
}