Cod sursa(job #756950)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 10 iunie 2012 19:42:49
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>
#include<algorithm>
using namespace std;


ifstream f("pscnv.in");
ofstream g("pscnv.out");
int X,Y,T[250000],n,m,a,b,k,i;
struct muchii{
	int x,y,c;
};
muchii v[500007];


struct  cmp{
	bool operator ()(const muchii a,const muchii b)const{
		return a.c<b.c;
	}
	
};
int tata(int x)
{
	if(x!=T[x])
		T[x]=tata(T[x]);
	return T[x];
}
int main () {
	
	f>>n>>m>>X>>Y;
	
	for(i=1;i<=m;i++){
		
		f>>v[i].x>>v[i].y>>v[i].c;
		
	}
	sort(v+1,v+1+m,cmp());
	
	
	for(i=1;i<=n;i++)
		T[i]=i;
	
	i=1;
	while(i<=m) {
		
		a=tata(v[i].x);
		b=tata(v[i].y);
		
		if(a!=b){
			if(v[i].c>k)
				k=v[i].c;
			T[b]=a;
		}
		if(T[X]==T[Y])
			break;
		i++;
	}
	g<<k<<"\n";
	return 0;
}