Cod sursa(job #2695196)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 12 ianuarie 2021 01:02:49
Problema PScNv Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 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++) {
        p=CC((*it).second.first);
        q=CC((*it).second.second);
        if(p!=q) {
            Un(p, q);
        }
        if(CC(x)==CC(y)) {
            cost=(*it).first; break;
        }
    }
    fprintf(f2, "%d\n", cost);
    fclose(f1); fclose(f2);
    return 0;
}