Cod sursa(job #982156)

Utilizator superman_01Avramescu Cristian superman_01 Data 8 august 2013 18:03:18
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 250005
#define KMAX 1005

using namespace std;

ifstream in("pscnv.in");
ofstream out("pscnv.out");

vector < pair < int , int > > G[NMAX];
int N,M, x , y , TT[NMAX];

int Find ( int x )
{
	int R ;
	for( R=TT[x] ; R!=TT[R]; R=TT[R]);
	return R;
}
void Unite ( int x , int y )
{
	TT[x] = y ;
}

int main ( void )
{
	int i ,  j ;
	int a , b , c;
	in>>N>>M>>x>>y;
	for( i = 1 ; i <= M ; ++i )
	{
		in>>a>>b>>c;
		G[c].push_back(make_pair(a,b));		
	}
	for( i = 1 ; i <= N ; ++i )
		TT[i] = i ;
	for( i = 1 ;  i <= 1005 ; ++i )
	{
		for( vector < pair < int , int > > :: iterator it = G[i].begin() ; it != G[i].end() ; ++it)
			if( Find(it->first) != Find( it->second) )
				Unite ( Find( it->first ) , Find(it->second)) ;
		if( Find( x ) == Find ( y ) )
		{
			out<<i<<"\n";
			return 0;
		}
	}
}