Prim算法求最小生成树

题目背景

给定一个 n 个点 m 条边的无向图，图中可能存在 重边 和 自环，边权可能为负数

求最小生成树的边权权重之和，如果不存在则输出 impossible

最小生成树

给定一张边带权的无向图 G = (V，E)，其中 V 表示图中点的集合，E表示图中边的集合，n = | V |，m = | E |

由 V 中的全部 n 个顶点和 E 中 n - 1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树

我的码码

Prim 算法用来解决 稀疏图 的最小生成树

Prime 算法的本质是 贪心，与 Dijkstra I 十分类似（Dijkstra I 是更新到起始点的距离，Prim 是更新到集合的距离），每次找出 不在集合内的，距离集合距离最小的点

如果当前的点，不是第一个的话，其到集合将会有一个距离 dis，dis 不为 0x3f3f3f3f 的话，证明此点可以走到集合，否则走不到

#include <bits/stdc++.h>

using namespace std;

const int N = 510;
int g[N][N]

int d[N];
// d[] 存的是每个点到集合的最短距离
bool st[N];
int n, m, a, b, c;

int prim() {
    int res = 0;

    for (int i = 1; i <= n; i++) {
        int t = -1;

        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || d[t] > d[j])) t = j;

        if (i != 1 && d[t] == 0x3f3f3f3f)   return 0x3f3f3f3f;
         // 此点无法抵达集合, 即无法生成最小生成树

        if (i != 1) res += d[t];
        st[t] = true;

        for (int j = 1; j <= n; j++)    d[j] = min(d[j], g[t][j]);
         /*
         此处便是 dijstra 与 prim 的区别
         dijstra 是存第 i 点到源点的最小距离 d[j] = min(d[j], d[t] + g[t][j])

         由于此时 t 点已经在集合里，所以
         prime 是存第 i 点到集合的最小距离 d[j] = min(d[j], g[t][j])
         */
    }

    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    memset(g, 0x3f, sizeof(g));
    memset(d, 0x3f, sizeof(d));

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);    // 无向图，邻接矩阵不仅存 a->b g[a][b] 还得存 b -> a g[b][a]
    }

    int k = prim();

    if (k == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << k << endl;

    return 0;
}