luogu
解法：Kruskal最小生成树； 在构建最小生成树时，如果 s 与 t 在一个集合里时，当前边就是答案（因为便是按照升序排的）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<vector> using namespace std; struct H{ int x,y; int cost; }a[20009]; int f[20009]; int find(int x) { if(f[x]==x) return x; return f[x]=find(f[x]); } int s,t,n,m,ans; int my_comp(const H&a,const H&b) { if(a.cost<b.cost) return 1; return 0; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[i].x=x,a[i].y=y,a[i].cost=z; } for(int i=1;i<=n;i++) f[i]=i; sort(a+1,a+m+1,my_comp); for(int p=1;p<=m;p++) { int c=find(a[p].x),b=find(a[p].y); f[c]=b; if(find(s)==find(t)) { ans=a[p].cost; break; } } printf("%d",ans); return 0; }