Cod sursa(job #1501036)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 22:51:32
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#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 ()
{
    ifstream fin ("pscnv.in" );
    ofstream fout("pscnv.out");

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

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

    return 0;
}