刚学OI1分钟的萌新84pts求助
查看原帖
刚学OI1分钟的萌新84pts求助
753837
Ginka_楼主2024/9/26 20:18
#include<bits/stdc++.h>
#define N 400400
#define int long long
#define inf 123456789
using namespace std;
int n,m,cnt,ans,num;
int head[N],nxt[N],to[N],wi[N];
int dis[N];
bool vis[N];
inline int read()
{
	int s=0,w=1;
	char x=getchar();
	while(x>'9'||x<'0') {if(x=='-') w=-1;x=getchar();}
	while(x<='9'&&x>='0') {s=s*10+x-'0';x=getchar();}
	return s*w;
}
void add(int x,int y,int z)
{
	cnt++;
	nxt[cnt]=head[x];
	head[x]=cnt;
	to[cnt]=y;
	wi[cnt]=z;
	return ;
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read();v=read();w=read();
		add(u,v,w);add(v,u,w);
	}
	for(int i=2;i<=n;i++)
	{
		dis[i]=inf;
	}
	for(int i=head[1];i;i=nxt[i])
	{
		dis[to[i]]=min(dis[to[i]],wi[i]);
	}
	int tot=1,now=1;
	while(tot++<n)
	{
		int minn=inf;
		vis[now]=true;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i]&&minn>dis[i])
			{
				minn=dis[i];
				now=i;
			}
		}
		ans+=minn;
		num++;
		for(int i=head[now];i;i=nxt[i])
		{
			int To=to[i];
			if(dis[To]>wi[i]&&!vis[To])
			{
				dis[To]=wi[i];
			}
		}
	}
	if(num==n-1) cout<<ans<<endl;
	else cout<<"orz";
	return 0;
}
2024/9/26 20:18
加载中...