Pagini recente » Cod sursa (job #2628593) | Cod sursa (job #939388) | Cod sursa (job #1914343) | Cod sursa (job #778721) | Cod sursa (job #496205)
Cod sursa(job #496205)
#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;
}