Cod sursa(job #959800)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 8 iunie 2013 20:29:51
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in ("pscnv.in");
ofstream out ("pscnv.out");

vector < pair <int, int> > Graf[1010];

int T[100010];

int find (int nod)
{
    if (nod == T[nod])
        return nod;

    return T[nod] = find (T[nod]);
}

int main()
{
    int N, M, S, D, i, j, a, b, c;

    in >> N >> M >> S >> D;
    while (M --){
        in >> a >> b >> c;
        Graf[c].push_back (make_pair (a, b));
    }

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

    for (i = 1; i <= 1000; i ++)
        for (auto it : Graf[i]){
            a = it.first;
            b = it.second;
            a = find (a);
            b = find (b);

            if (a != b)
                T[a] = b;

            if (find (S) == find (D)){
                out << i;
                return 0;
            }
        }

    return 0;
}