86分求调
查看原帖
86分求调
1068781
wangxx2012楼主2025/7/22 09:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,head[1000010],gs[10000010],dis[1000010];
int k;
bool vis[1000010];
struct node{
	int to,next,w;
}edge[1000010];
void adde(int u,int v,int w){
	edge[++k].to=v;
	edge[k].w=w;
	edge[k].next=head[u];
	head[u]=k;
}
int prim(){
	int v,ans=0;
	int cnt=0;
	memset(dis,0x3f,sizeof(vis));
	memset(vis,0,sizeof(vis));
	vis[1]=1; dis[1]=0;
	cnt++;
	for(int i=head[1];i;i=edge[i].next){
		v=edge[i].to;
		dis[v]=edge[i].w;
	}
	for(int i=1;i<n;i++){
		int minn=INT_MAX,id;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&minn>dis[j]){
				minn=dis[j]; id=j;
			}
		}
		if(minn==INT_MAX) break;
		ans+=minn; vis[id]=1;
		cnt++;
		for(int j=head[id];j;j=edge[j].next){
			v=edge[j].to;
			if(dis[v]>edge[j].w&&!vis[v]) dis[v]=edge[j].w; 
		}
	}
	if(cnt<n) return -1;
	return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		adde(x,y,z); adde(y,x,z);
	}
	int x=prim();
	if(x!=-1) cout<<x;
	else cout<<"orz";
	return 0;
	}

2025/7/22 09:34
加载中...