图论 MST(最小生成树) prim

#include <bits/stdc++.h>
using namespace std;
const int P = 1e6 + 7;
const int inf = 1e9;
typedef long long ll;
int mp[1010][1010];
int n, m;
int d[1010];//从已选点到i的min权值
int vis[1010];//选或没选
void prim()
{
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[1] = 0;
	//开始选1
	int ans = 0;
	for (int s = 1; s <= n; s++)
	{
		//选n个点
		int mi = inf; int id = -1;
		for (int i = 1; i <= n; i++)
		{
			if (d[i] < mi&&vis[i]==0)
			{
				mi = d[i];
				id = i;
			}
		}
		if (id == -1)
		{
			cout << -1; return;
		}
		ans += mi;
		vis[id] = 1;
		//更新d数组
		for (int i = 1; i <= n; i++)
		{
			if (vis[i] == 0 && mp[id][i] < d[i])
				d[i] = mp[id][i];
		}
	}
	cout << ans;
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;

	//防止重边
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			mp[i][j] = inf;
		}
	}
	for (int i = 1; i <= m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if(mp[a][b]>c)
			mp[a][b] = mp[b][a] = c;
	}
	prim();
	return 0;
}