Cod sursa(job #1500977)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 22:16:50
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define x first
#define y second.first
#define z second.second
using namespace std;

const int DIM1 = 200010;
const int DIM2 = 500010;

int N, M, start, finish, Father[DIM1];
pair <int, pair <int, int> > Edge[DIM2];

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

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

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

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

    for (int i = 1; i <= M; i ++)
    {
        swap (Edge[i].x, Edge[i].y);
        swap (Edge[i].y, Edge[i].z);

        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);
            return 0;
        }
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}