Pagini recente » Cod sursa (job #597079) | Cod sursa (job #1924005) | Cod sursa (job #2499714) | Cod sursa (job #410968) | Cod sursa (job #934469)
Cod sursa(job #934469)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define Nmax 250005
#define Mmax 500005
struct S{
int x;
int y;
int c;
} A[Mmax], Aux[Mmax];
int RANG[Nmax], TATA[Nmax];
int N, M, RES, X, Y;
void MergeSort( int st, int dr ){
int m = ( st + dr ) / 2;
if ( st == dr )
return;
MergeSort( st, m );
MergeSort( m + 1, dr );
for ( int i = st, j = m + 1, k = st; i <= m || j <= dr; )
if ( j > dr || ( i <= m && A[i].c <= A[j].c ) )
Aux[k++] = A[i++];
else
Aux[k++] = A[j++];
for ( int k = st; k <= dr; k++ )
A[k] = Aux[k];
}
int gaseste( int x ){
int R, y;
for( R = x; TATA[R] != R; R = TATA[R] );
for( ; TATA[x] != x; ){
y = TATA[x];
TATA[x] = R;
x = y;
}
return R;
}
void uneste ( int x, int y ){
if ( RANG[x] > RANG[y] )
TATA[y] = x;
else
TATA[x] = y;
if ( RANG[x] == RANG[y] )
RANG[y]++;
}
void init(){
for ( int i = 1; i <= N; i++ )
TATA[i] = i,
RANG[i] = 1;
}
void Kruskal(){
for ( int i = 1; i <= M; i++ ){
int a = gaseste ( A[i].x );
int b = gaseste ( A[i].y );
if ( a != b )
uneste ( a, b );
if ( gaseste( X ) == gaseste ( Y ) ){
RES = A[i].c;
return;
}
}
}
void citire(){
ifstream f("pscnv.in");
f >> N >> M >> X >> Y;
for ( int i = 1; i <= M; i++ )
f >> A[i].x >> A[i].y >> A[i].c;
f.close();
}
void afis(){
ofstream g("pscnv.out");
g << RES << "\n";
g.close();
}
int main(){
citire();
MergeSort( 1, M );
init();
Kruskal();
afis();
return 0;
}