Pagini recente » Cod sursa (job #409094) | Cod sursa (job #466515) | Cod sursa (job #1040770) | Cod sursa (job #1610789) | Cod sursa (job #2121184)
#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;
}