Prim30分求助!
查看原帖
Prim30分求助!
716721
leo12334楼主2023/1/2 21:46

不知道为什么只有最后三个测试点通过了,想请教一下各位大佬

#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;
} 
2023/1/2 21:46
加载中...