Cod sursa(job #1500988)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 22:24:07
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 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];

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

inline bool cmp (const str &node1, const str &node2)
{
    if (node1.z < node2.z)
        return 1;
    return 0;
}

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", &Edge[i].x);
        scanf ("%d", &Edge[i].y);
        scanf ("%d", &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[Edge[i].y] = Father[Father[Edge[i].x]];

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

    fclose (stdin );
    fclose (stdout);

    return 0;
}