leo12334 @ 2023-01-02 21:46:48
不知道为什么只有最后三个测试点通过了,想请教一下各位大佬
#include<bits/stdc++.h>
using namespace std;
#define maxn 234567
int n,m,cnt,x,y,w,ans,vis[maxn],head[maxn],dis[maxn];
struct node{
int to,next,w;
}e[maxn];
void add(int x,int y,int w){
e[++cnt].next=head[x];
e[cnt].to=y;
e[cnt].w=w;
head[x]=cnt;
}
int main(){
cin>>n>>m;
if(m<n-1){cout<<"orz";return 0;}
for(int i=1;i<=n;i++){
cin>>x>>y>>w;
add(x,y,w);
add(y,x,w);
}
int k=0;
vis[1]=1;
for(int i=1;i<=n;i++) dis[i]=1e9;
for(int i=head[1];i;i=e[i].next)
dis[e[i].to]=min(e[i].w,dis[e[i].to]);
while(++k<=n-1){
int now=1,minn=1e9;
for(int i=1;i<=n;i++){
if(!vis[i]&&dis[i]<minn){
minn=dis[i];
now=i;
}
}
vis[now]=1;
ans+=minn;
for(int i=head[now];i;i=e[i].next){
int y=e[i].to;
dis[y]=min(dis[y],e[i].w);
}
}
for(int i=1;i<=n;i++)
if(!vis[i]){
cout<<"orz";return 0;
}
cout<<ans<<endl;
}