这份代码79分,#8 #9 #10wa了
查看原帖
这份代码79分,#8 #9 #10wa了
736900
lishitang楼主2023/6/21 20:13
#include<iostream>
using namespace std;
struct edge{
	int v,nxt,w;
}e[200000];

int tot,ans,n,m,head[5005],cnt,dis[5005],vis[5005];



void add(int u,int v,int w){
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].v=v;
	e[cnt].w=w;
	head[u]=cnt;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)dis[i]=1e9;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dis[1]=0;
	dis[0]=1e9;
	while(1){
		int u=0;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&dis[i]<dis[u])u=i;
		if(!u)break;
		tot++;vis[u]=1;ans+=dis[u];
		for(int i=head[u];i;i=e[i].nxt){
			if(dis[e[i].v]>e[i].w){
				dis[e[i].v]=e[i].w;
			}
		}
	}
	if(tot==n)
		cout<<ans<<endl;
	else 
		cout<<"orz"<<endl;
		
	
	return 0;
}
2023/6/21 20:13
加载中...