最小生成树之Prim算法

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int vis[maxn], d[maxn], mat[maxn][maxn];
int n, cur, ans = 0;
int main() {
   
	scanf("%d", &n);
	for (int i = 1;i <= n;++i) {
   
		for (int j = 1;j <= n;++j) {
   
			scanf("%d", &mat[i][j]);//读入邻接矩阵
		}
	}
	memset(vis, 0, sizeof(vis));//初始化
	memset(d, INF, sizeof(d));//初始化
	d[1] = 0;//第一个顶点到自己的距离为0
	for (int i = 1;i <= n;++i) {
   
		cur = -1;
		for (int j = 1;j <= n;++j) {
   
			if (!vis[j] && (cur == -1 || d[cur] > d[j])) {
   
				cur = j;//维护当前树所能到达的顶点的路径最小值所对应的顶点
			}
		}
		ans += d[cur];
		vis[cur] = 1;//标记此顶点已访问过
		for (int j = 1;j <= n;++j) {
   
			if (!vis[j] && d[j] > mat[cur][j]) {
   
				d[j] = mat[cur][j];//如果最新入树的顶点到其相连顶点的距离小于旧树到
				//对应顶点的距离 则更新最小值
			}
		}
	}
	printf("%d", ans);
	return 0;
}