Cod sursa(job #1501061)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 23:04:18
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int DIM = 250006;

int N, M, start, finish, F[DIM];

struct str {
    int x;
    int y;
    int z;
}; str V[DIM * 2];

int f (int X)
{
    if (X != F[X])
        F[X] = f (F[X]);
    return F[X];
}

int cmp (str a, str b)
{
    return a.z < b.z;
}

int main ()
{
    freopen ("pscnv.in" ,"r", stdin );
    freopen ("pscnv.out","w", stdout);

    scanf ("%d %d", &N, &M);
    scanf ("%d %d", &start, &finish);

    for (int i = 1; i <= M; i ++)
        scanf ("%d %d %d", &V[i].x, &V[i].y, &V[i].z);

    sort (V + 1, V + M + 1, cmp);

    for (int i = 1; i <= N; i ++)
        F[i] = i;

    for (int i = 1; i <= M; i ++)
    {
        if (f(V[i].x) != f(V[i].y))
            F[F[V[i].x]] = F[V[i].y];

        if (f(start) == f(finish))
        {
            printf ("%d\n", V[i].z);
            break;
        }
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}