1923

1923

//  1923 - 躲避拥堵的最佳路线 ---并查集，二分答案
// 来源： 东方博宜oj  oj.czos
#include<bits/stdc++.h>
using namespace std;
/*经过道路的拥挤度的最大值最小（二分答案）
*///思路
1，二分最大拥挤度：l=min(拥挤度)，r=max(拥挤度)；
2，check(mid):检验当最大拥挤度为mid时，能否从s区到t区；（1）将所有道路中拥挤度<=mid的道路修起来（合并）（2）查询s和t是否在一个集合
3，求二分的左边界
//代码
const int N=1e4+10;
int n,m,s,t;
int fa[N];
int l=INT_MAX,r=INT_MIN,mid;
struct node
{int x,y,len;
}a[2*N];
int findd(int x)
{if(fa[x]==x) return x;else return fa[x]=findd(fa[x]);
}
void mergee(int x,int y)
{int fx=findd(x);int fy=findd(y);if(fx!=fy) fa[fx]=fy;
}
bool check(int mid)
{//初始化for(int i=1;i<=n;i++) fa[i]=i;//修路for(int i=1;i<=m;i++){if(a[i].len<=mid) mergee(a[i].x,a[i].y);}// 判断s能否去t,如果在一个集合就能去return findd(s)==findd(t);
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].len;l=min(l,a[i].len);r=max(r,a[i].len);}//二分答案while(l<=r){mid=l+r>>1;if(check(mid)) r=mid-1;else l=mid+1;}cout<< l;return 0;
}