Cod sursa(job #1501058)

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

#define DIM1 200010
#define DIM2 500010
using namespace std;

int N, M, start, finish, Father[DIM1];

struct str {
    int x;
    int y;
    int z;
} Edge[DIM2];

int findFather (int node)
{
    if (node != Father[node])
        Father[node] = findFather(Father[node]);
    return Father[node];
}

int cmp (str node1, str node2)
{
    return node1.z < node2.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", &Edge[i].x, &Edge[i].y, &Edge[i].z);

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

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

    for (int i = 1; i <= M; i ++)
    {
        if (findFather(Edge[i].x) != findFather(Edge[i].y))
            Father[Father[Edge[i].x]] = Father[Edge[i].y];

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

    fclose (stdin );
    fclose (stdout);

    return 0;
}