我用的是Kruskal,写完以后输入样例,竟然没有输出?求助大佬! 代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4;
int n,m,s,t,b=0;
int fa[maxn];
struct node{
int u,v,w;
bool operator<(const node &x)const{
return w<x.w;
}
}edge[maxn];
void addEdge(int u,int v,int w){
edge[++s]=(node){u,v,w};
}
void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
}
}
int get(int x){
return fa[x]=(fa[x]==x)?x:get(fa[x]);
}
void merch(int x,int y){
x=get(x);
y=get(y);
if(x!=y){
fa[y]=x;
}
}
int main(){
cin>>n>>m>>s>>t;
init();
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
sort(edge+1,edge+1+m);
for(int i=1;i<=m;i++){
if(get(edge[i].u)!=get(edge[i].v)){
merch(edge[i].u,edge[i].v);
/*for(int i=1;i<=n;i++){
cout<<get(i)<<" ";
}
cout<<endl;*/
}
if(get(t)==get(s)){
//cout<<1<<endl;
cout<<edge[i].w<<endl;
return 0;
}
}
return 0;
}
望大佬们指点迷津