Cod sursa(job #496205)

Utilizator klamathixMihai Calancea klamathix Data 28 octombrie 2010 09:32:17
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<vector>
const int maxval = 1005;
using namespace std;

vector < pair<int,int> > G[maxval];
int i , j , n , m , x , y  , a  , b , c, dad[250001] , rang[250001];

int find (int A ) {
	int root = A;
	for( ; root != dad[root] ; root = dad[root]);
	for( ; A != dad[A] ; ) {
		int aux = dad[A];
		dad[A] = root;
		A = aux;
	}
return root;
}

void unite( int A , int B ) {
	if ( rang[A] > rang[B]) 
		dad[B] = A;
	else
		dad[A] = B;
	if ( rang[A] == rang[B])
		rang[B]++;
}

int main()
{
	freopen("pscnv.in","r",stdin);
	freopen("pscnv.out","w",stdout);
	
	scanf("%d %d %d %d",&n,&m,&x,&y);
	for( i = 1 ; i <= n ; ++i ) dad[i] = i , rang[i] = 1;
	for ( i = 1 ; i <= m ; ++i ) {
		scanf("%d %d %d",&a,&b,&c);
		G[c].push_back(make_pair(a,b));
	}
	
	for ( i = 1 ; i <= 1000 ; ++i ) {
		for( j = 0 ; j < G[i].size() ; ++j) {
			unite( find(G[i][j].first) ,find(G[i][j].second));
			if ( find(x) == find(y) ) {
				printf("%d\n",i);
				return 0;
			}
		}
	}
	
return 0;
}