Cod sursa(job #407911)

Utilizator vladiiIonescu Vlad vladii Data 2 martie 2010 18:37:04
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#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() {
    FILE *f1=fopen("pscnv.in", "r"), *f2=fopen("pscnv.out", "w");
    int i, j, p, q, c, cost;
    fscanf(f1, "%d%d%d%d", &N, &M, &x, &y);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d%d%d", &p, &q, &c);
         G.push_back(make_pair(c, make_pair(p, q)));
    }
    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;
         }
    }
    fprintf(f2, "%d\n", cost);
    fclose(f1); fclose(f2);
    return 0;
}