求调 码风良好
查看原帖
求调 码风良好
1108111
XYY62012楼主2024/11/20 20:39
#include<bits/stdc++.h>
using namespace std;
const int N=5500;
int n,m;
int k,num,sum;
int head[N],vis[N],f[N];
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
struct Edge{
	int to;
	int next;
	int w;
}d[596200];
void add(int a,int b,int c){
	d[++k].to=b;
	d[k].w=c;
	d[k].next=head[a];
	head[a]=k;
}
void prim(){
	f[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty() && num<=n){
		int a=q.top().first,b=q.top().second;
		q.pop();
		if(vis[b]){
			continue;
		} 
        num++;
        sum+=a;
        vis[b]=1;
        for(int i=head[b];i!=-1;i=d[i].next){
        	if(d[i].w<f[d[i].to]){
        		f[d[i].to]=d[i].w,q.push(make_pair(f[d[i].to],d[i].to));
			}
                
	}
		}
            
}
int main(){
	cin>>n>>m;
	memset(f,596200,sizeof(f));
    memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	prim();
	  if(num==n){
	  	cout<<sum<<endl;
	}else{
		cout<<"orz"<<endl;
	} 
	return 0;
}
2024/11/20 20:39
加载中...