prim求助
查看原帖
prim求助
1270559
zkhehe楼主2024/1/27 20:40
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
#define N 2000005
int n,m,cnt=0,sum=0;
int dis[N],vis[N];
int u[N],v[N],w[N],first[N],nxt[N];
int p[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		first[i]=-1;
		dis[i]=1e9;
		vis[i]=0;
	}
	for(int i=1;i<=m*2;i=i+2){
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		v[i+1]=u[i];
		u[i+1]=v[i];
		w[i+1]=w[i];
		nxt[i]=first[u[i]];
		first[u[i]]=i;
		nxt[i+1]=first[u[i+1]];
		first[u[i+1]]=i+1;
	}
	vis[1]=1;
	int k=first[1];
	while(k!=-1){
		dis[u[k]]=w[k];
		k=nxt[k];
	}
	int sum=0;
	while(cnt<n){
		int minn=N;
		int j;
		for(int i=1;i<=n;i++){
			if(dis[i]<minn&&vis[i]==0){
				minn=dis[i];
				j=i;
			}
		}
		cnt++;
		sum+=minn;
		vis[j]=1;
		k=first[j];
		while(k!=-1){
			dis[u[k]]=min(dis[u[k]],w[k]);
			k=nxt[k];
		}
	}
	cout<<sum;
	return 0;
}
2024/1/27 20:40
加载中...