Cod sursa(job #1501074)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 23:13:31
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

ifstream fin ("pscnv.in" );
ofstream fout("pscnv.out");

const int DIM = 250006;

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

int N, M, start, finish, F[DIM];
char S[20];

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

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

void read (int &X)
{
    X = 0;
    memset (S, 0, sizeof(S));
    fin >> S + 1;

    for (int i = 1; S[i]; i ++)
        X = X * 10 + (S[i] - '0');
    return;
}

int main ()
{

    read (N); read (M);
    read (start); read (finish);

    for (int i = 1; i <= M; i ++)
    {
        read (V[i].x);
        read (V[i].y);
        read (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[V[i].y] = F[V[i].x];

        if (f(start) == f(finish))
        {
           fout << V[i].z;
            break;
        }
    }

    return 0;
}