题意为考虑选取某个值以下的所有边使得1到n联通,使用并查集维护连通块信息,先将边按边权排序,直到1和n连通为止,模拟并查集合并的过程即可。也可使用迪杰斯特拉,二分答案加bfs等等做法,均可以通过此题。
#include <bits/stdc++.h>
using namespace std;
int p[400050];
int n,m;
struct edge
{
int u,v,w;
/* data */
}e[500050];
bool cmp(edge l,edge r){
return l.w<r.w;
}
int find(int x){
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
void merge(int l,int r){
int fl=find(l),fr=find(r);
if(fl==fr)return ;
p[fl]=p[fr];
return ;
}
int main(){
// freopen("8.in","r",stdin);
// freopen("8.out","w",stdout);
cin>>n>>m;
for(int x=1;x<=m;x++){
cin>>e[x].u>>e[x].v>>e[x].w;
}
sort(e+1,e+m+1,cmp);
for(int x=1;x<=n;x++){
p[x]=x;
}
int ans=0;
while(find(1)!=find(n)){
ans++;
merge(e[ans].u,e[ans].v);
}
cout<<e[ans].w<<"\n";
return 0;
}