Cod sursa(job #1500965)

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

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

int N, M, start, finish, Father[DIM]; char String[10];
pair <int, pair <int, int> > Edge[DIM];

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

inline void read (int &value)
{
    value = 0;
    memset (String, 0, sizeof(String));
    scanf ("%s", String + 1);

    for (int i = 1; String[i]; i ++)
        value = value * 10 + (String[i] - '0');

    return;
}

int main ()
{
    freopen ("pscnv.in" ,"r", stdin );
    freopen ("pscnv.out","w", stdout);

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

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