prim最小生成树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=400005;
const ll maxm=999999999;
ll n,m,cnt=1,dis[maxn],head[maxn];
bool vis[maxn];
struct edge{
	ll to,w,nxt;
}d[maxn*2];
void add(int u,int v,int w)
{
	d[cnt].nxt=head[u];
	d[cnt].to=v;
	d[cnt].w=w;
	head[u]=cnt++;
}
ll prim()
{
	for(int i=0;i<=n;i++)	dis[i]=maxm;
	dis[1]=0;
	for(int i=head[1];i;i=d[i].nxt)//可能有重边 
		dis[d[i].to]=min(dis[d[i].to],d[i].w);
	int tot=0,num=1,ans=0;
	while(++tot<n)
	{
		ll minn=maxm;
		vis[num]=1;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==0&&minn>dis[i])
				minn=dis[i],num=i;
		}
		ans+=minn;
		for(int i=head[num];i;i=d[i].nxt)
		{
			if(dis[d[i].to]>d[i].w&&!vis[d[i].to])
				dis[d[i].to]=d[i].w;
		}
	}
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,w;
		cin>>l>>r>>w;
		add(l,r,w);
		add(r,l,w);
	}
	cout<<prim();
}