Cod sursa(job #952372)

Utilizator vendettaSalajan Razvan vendetta Data 23 mai 2013 10:31:13
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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
#define Cifmax (1<<14)

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

void next(){
    ++poz; if (poz == Cifmax){
        fread(S, 1, Cifmax, stdin);
        poz = 0;
    }
}

void buf(int &nr){
    nr = 0;
    for(; S[poz]<'0' || S[poz]>'9'; next());
    for(; S[poz]>='0' && S[poz]<='9'; next()){
        nr = nr * 10 + (S[poz] - '0');
    }
}

void citeste(){
    buf(n); buf(m); buf(start); buf(final);
    int x, y, c;
    for(int i=1; i<=m; ++i){
        buf(x); buf(y); buf(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";
            return;
        }
    }
}

int main(){
    freopen("pscnv.in", "r", stdin);
    citeste();
    rezolva();

    fclose(stdin);
    g.close();

    return 0;
}