Cod sursa(job #1527244)

Utilizator livliviLivia Magureanu livlivi Data 17 noiembrie 2015 22:31:51
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<algorithm>
#define N 250000
#define M 500000
using namespace std;

class mazi{
public:
    int cost,nod1,nod2;

    bool operator > (const mazi a) const{
        if (cost>a.cost) return true;
        return false;
    }
    bool operator < (const mazi a) const{
        if (cost<a.cost) return true;
        return false;
    }
};


mazi muchii[M+1];
int rad[N+1];

int stramos(int nod){
    if (rad[nod]==0) return nod;
    else {
        rad[nod]=stramos(rad[nod]);
        return rad[nod];
    }
}


int main(){
    freopen ("pscnv.in","r",stdin);
    freopen ("pscnv.out","w",stdout);
    int n,m,i,x,y,a,b;

    scanf ("%d%d%d%d",&n,&m,&x,&y);

    for(i=1;i<=m;i++)
        scanf ("%d%d%d",&muchii[i].nod1,&muchii[i].nod2,&muchii[i].cost);

    sort(muchii+1,muchii+m+1);

    i=0;
    while(stramos(x)!=stramos(y) &&i<m){
        i++;

        a=stramos(muchii[i].nod1);
        b=stramos(muchii[i].nod2);
        if (a!=b) rad[b]=a;
    }

    printf ("%d",muchii[i].cost);
    return 0;
}