Cod sursa(job #992726)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 2 septembrie 2013 14:57:57
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MAXN = 250005;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, M, S, T, Father[MAXN];
vector< pair<int, pair<int, int> > > Edge;

inline int Find(int x) {
    if(Father[x] != x)
        Father[x] = Find(Father[x]);
    return Father[x];
}

int main() {
    cin >> N >> M >> S >> T;
    for(int i = 0 ; i < M ; ++ i) {
        int x, y, z;
        cin >> x >> y >> z;
        Edge.push_back(make_pair(z, make_pair(x, y)));
    }
    for(int  i = 1 ; i <= N ; ++ i)
        Father[i] = i;
    sort(Edge.begin(), Edge.end());
    for(int i = 0 ; i < M ; ++ i) {
        int x = Edge[i].second.first,
            y = Edge[i].second.second,
            z = Edge[i].first;
        int Tx = Find(x),
            Ty = Find(y);
        if(Tx != Ty)
            Father[Tx] = Ty;
        if(Find(S) == Find(T)) {
            cout << z << '\n';
            return 0;
        }
    }
    cin.close();
    cout.close();

    return 0;
}