Cod sursa(job #2121184)

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

int n, m, a, b, Sol;
bool ok = 0;
int TT[250005], RG[250005], C[250005];
bool f[250005];
vector <pair <int, int> > v[250005];
struct muchie{
    int x, y, k;
    bool operator < (const muchie &aux)const{
        return k < aux.k;
    }
};
muchie e[500005];
inline void dfs(int nod, int Max){
    if(nod == b){
        Sol = Max;
        ok = 1;
        return ;
    }
    for(auto it : v[nod]){
        if(f[it.first]) continue ;
        f[it.first] = 1;
        dfs(it.first, max(Max, it.second));
        if(ok == 1) return ;
    }
}
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));
            v[e[i].x].push_back({e[i].y, e[i].k});
            v[e[i].y].push_back({e[i].x, e[i].k});
        }
    }
    dfs(a, 0);
    printf("%d", Sol);
    return 0;
}