Cod sursa(job #1501069)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 23:10:17
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#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];

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;
}

int main ()
{

    fin >> N >> M;
    fin >> start >> finish;

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

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

    return 0;
}