最小生成树之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;
}