Cod sursa(job #1629623)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 4 martie 2016 17:06:56
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#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;
}