Cod sursa(job #960625)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 20:29:28
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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[250010];
 
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;
}