Cod sursa(job #952367)

Utilizator vendettaSalajan Razvan vendetta Data 23 mai 2013 10:26:15
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define nmax 250005
#define Mmax 500005

int n, m, start, final, t[nmax];
vector< pair<int, pair<int,int> > > edge;

void citeste(){
    f >> n >> m >> start >> final;
    int x, y, c;
    for(int i=1; i<=m; ++i){
        f >> x >> y >> c;
        edge.push_back( make_pair( c, make_pair(x, y) ) );
    }
}

inline int afla(int x){
    int x2 = x;
    for(; t[x] != 0; x = t[x]);
    int temp = 0;
    while(x2 != x){
        temp = t[x2]; t[x2] = x; x2 = temp;
    }
    return x;
}

void uneste(int x, int y){
    t[y] = x;
}

void rezolva(){
    sort(edge.begin(), edge.end());

    for(int i=0; i<m; ++i){
        int radX = afla(edge[i].second.first);
        int radY = afla(edge[i].second.second);
        if (radX == radY) continue;
        uneste(radX, radY); // x -> y;
        if ( afla(start) == afla(final) ) {
            g << edge[i].first << "\n";
            //cout << edge[i].first << "\n";
            return;
        }
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}