C++primRE求调
查看原帖
C++primRE求调
1048193
PengDave楼主2024/2/24 22:04
#include<iostream>
#include<cstring>
using namespace std;
struct edge{
	int v;
	int nxt;
	int to;
}a[200010];
int head[5005];
int dis[5005];
int cnt=0;
bool vis[5005];
void add(int x,int y,int z){
	cnt++;
	a[cnt].nxt=head[x];
	a[cnt].to=y;
	a[cnt].v=z;
	head[x]=cnt;
	return;
}
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int p,q,t;
		cin>>p>>q>>t;
		add(p,q,t);
		add(q,p,t);
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	int tot=0;
	for(int i=head[1];i;i=a[i].nxt){
		dis[a[i].to]=min(dis[a[i].to],a[i].v);
	}
	vis[1]=1;
	int ans=0;
	for(int i=1;i<n;i++){
		int minn=0x3f3f3f3f,u=0;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]<minn){
				minn=dis[j];
				u=j;
			}
		}
		if(minn==0x3f3f3f3f){
			cout<<"orz"<<endl;
			return 0;
		}
		tot++;
		ans+=dis[u];
		vis[u]=1;
		for(int j=head[u];j;j=a[j].nxt){
			if(!vis[a[j].to]){
				dis[a[j].to]=min(dis[a[j].to],a[j].v);
			}
		}
	}
	if(tot==n-1){
		cout<<ans<<endl;
	}else{
		cout<<"orz"<<endl;
	}
	return 0;
}
2024/2/24 22:04
加载中...