Cod sursa(job #2121185)

Utilizator giotoPopescu Ioan gioto Data 3 februarie 2018 13:53:31
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, a, b;
int TT[250005], RG[250005];
struct muchie{
    int x, y, k;
    bool operator < (const muchie &aux)const{
        return k < aux.k;
    }
};
muchie e[500005];
inline int find(int x){
    int R = x;
    for(R; R != TT[R] ; R = TT[R]) ;
    while(x != TT[x]){
        int y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}
inline void unite(int x, int y){
    if(RG[x] > RG[y]) TT[y] = x;
    else TT[x] = y;
    if(RG[x] == RG[y]) ++RG[y];
}
int main()
{
    freopen("pscnv.in", "r", stdin);
    freopen("pscnv.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    int x, y, k, NR = 0;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &k);
        if(x == y) continue ;
        e[i] = {x, y, k};
    }
    for(int i = 1; i <= n ; ++i) TT[i] = i, RG[i] = 1;
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= m ; ++i){
        if(find(e[i].x) != find(e[i].y)){
            unite(find(e[i].x), find(e[i].y));
            if(find(a) == find(b)) {printf("%d", e[i].k); return 0;}
        }
    }
    return 0;
}