Pagini recente » Cod sursa (job #1048934) | Cod sursa (job #232132) | Cod sursa (job #1432628) | Cod sursa (job #1433422) | Cod sursa (job #2121185)
#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;
}