最小生成树prim

1.dist[首点] = 0, 有 n 个点就循环 n 次。

2.每次循环找到距离集合最近的点(设这点为 x 点，第一次循环找到的 x 点为首点)，找到后做两件事：加上这点的距离，用这点取更新其他的 dist[i]。

3.更新后的 dist[i] 为其他点到包含刚才找到的 x 点的新集合的最近距离

AcWing 858. Prim算法求最小生成树

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5e2 + 10, INF = 0x3f3f3f3f;

int st[N], g[N][N], dist[N];
int n, m;

void prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    int sum = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
        {
            if (st[j] == 0 && (t == -1 || dist[j] < dist[t]))
               t = j;
        }

        st[t] = 1;

        if (dist[t] == INF) 
        {
            cout << "impossible";
            return ;
        }

        sum += dist[t];

        for (int j = 1; j <= n; j ++ ) 
            dist[j] = min(dist[j], g[t][j]);
    }

    cout << sum;
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    for (int i = 1; i <= m; i ++ ) 
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x][y] = g[y][x] = min(g[x][y], w);
    }

    prim();

    return 0;
}