Cod sursa(job #1737365)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 3 august 2016 21:08:26
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
#include<algorithm>
#define MAXN 250010
#define MAXM 500010
using namespace std;
struct Edge{
    int a,b,c;
};
Edge edge[MAXM];
bool Compare(const Edge &a,const Edge &b){
    return a.c<b.c;
}
int dad[MAXN];
int FindDad(int node){
    if(dad[node]==node)
        return node;
    return dad[node]=FindDad(dad[node]);
}
int main(){
    freopen("pscnv.in","r",stdin);
    freopen("pscnv.out","w",stdout);
    int n,m,x,y,i;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(i=1;i<=n;i++)
        dad[i]=i;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
    sort(edge+1,edge+m+1,Compare);
    i=0;
    while(FindDad(x)!=FindDad(y)){
        if(FindDad(edge[i].a)!=FindDad(edge[i].b))
            dad[edge[i].a]=edge[i].b;
        i++;
    }
    printf("%d",edge[i-1].c);
    return 0;
}