Pagini recente » Cod sursa (job #1070586) | Cod sursa (job #1056834) | Cod sursa (job #2920697) | Cod sursa (job #2560991) | Cod sursa (job #1629623)
#include<cstdio>
#include<algorithm>
using namespace std;
FILE *fin = fopen( "pscnv.in", "r" ), *fout = fopen( "pscnv.out", "w" );
const int Size = 30 * 1e6;
const int nmax = 250000;
const int mmax = 2 * nmax;
int pos;
char buff[ Size ];
int tata[ nmax + 1 ], grad[ nmax + 1 ];
struct muchie{
int x, y, k;
} v[ mmax + 1 ];
inline bool operator < ( const muchie &a, const muchie &b ) {
return ( a.k < b.k );
}
char next_pos() {
++ pos;
if ( pos == Size ) {
fread( buff, Size, 1, fin );
pos = 0;
}
return buff[ pos ];
}
int get_nmb() {
char c = next_pos();
while ( c < '0' || c > '9' ) {
c = next_pos();
}
int x = 0;
while ( c >= '0' && c <= '9' ) {
x = x * 10 + c - '0';
c = next_pos();
}
return x;
}
int find_tata( int x ) {
if ( x == tata[ x ] ) {
return x;
}
return ( tata[ x ] = find_tata( tata[ x ] ) );
}
int main() {
int n, m, a, b;
pos = Size - 1;
n = get_nmb(); m = get_nmb(); a = get_nmb(); b = get_nmb();
for( int i = 0; i < m; ++ i ) {
v[ i ].x = get_nmb();
v[ i ].y = get_nmb();
v[ i ].k = get_nmb();
}
sort( v, v + m );
for( int i = 1; i <= n; ++ i ) {
tata[ i ] = i;
grad[ i ] = 1;
}
for( int i = 0; i < m; ++ i ) {
int ta = find_tata( v[ i ].x ), tb = find_tata( v[ i ].y );
if ( ta != tb ) {
if ( grad[ ta ] < grad[ tb ] ) {
ta ^= tb ^= ta ^= tb;
}
tata[ tb ] = ta;
grad[ ta ] += grad[ tb ];
}
if ( find_tata( a ) == find_tata( b ) ) {
fprintf( fout, "%d\n", v[ i ].k );
break;
}
}
fclose( fin );
fclose( fout );
return 0;
}