Cod sursa(job #407908)

Utilizator vladiiIonescu Vlad vladii Data 2 martie 2010 18:34:32
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N, M, x, y;
int Arb[250001], H[250001];
vector<pair<int, pair<int, int> > > G;

int CC(int nod) {
    while(Arb[nod]!=nod) {
        nod=Arb[nod];
    }
    return nod;
}

void Un(int p, int q) {
    if(H[p]>H[q]) {
         Arb[q]=p;
    }
    else {
         Arb[p]=q;
    } 
    if(H[p]==H[q]) { H[p]++; } 
}

int main() {
    fstream f1, f2;
    int i, j, p, q, c, cost;
    f1.open("pscnv.in", ios::in);
    f1>>N>>M>>x>>y;
    for(i=1; i<=M; i++) {
         f1>>p>>q>>c;
         G.push_back(make_pair(c, make_pair(p, q)));
    }
    f1.close();
    for(i=1; i<=N; i++) {
         Arb[i]=i; H[i]=1;
    }
    sort(G.begin(), G.end()); //sortez dupa cost
    for(vector<pair<int, pair<int, int> > >::iterator it=G.begin(); it!=G.end(); it++) {
         if(CC((*it).second.first)!=CC((*it).second.second)) {
              Un((*it).second.first, (*it).second.second);
         }
         if(CC(x)==CC(y)) {
              cost=(*it).first; break;
         }
    }
    f2.open("pscnv.out", ios::out);
    f2<<cost<<endl;
    f2.close();
    return 0;
}