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

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int dis[N], mp[N][N];
bool vis[N];
int n, m;

struct Node {
    int to, w;
};

vector<Node> g[510];

int prim() {
    memset(dis, 0x3f, sizeof dis);
    int res = 0;
    for (int _ = 0; _ < n; _++) {
        int t = -1;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (t == -1 || dis[i] < dis[t]))
                t = i;
        if (dis[t] == INF && _) return INF;
        if(_) res += dis[t];
        for (int i = 1; i <= n; i++)
            dis[i] = min(mp[t][i], dis[i]);
        vis[t] = 1;
    }
    return res;
}


int main() {
    cin >> n >> m;
    memset(mp, 0x3f, sizeof mp);
    for (int i = 1; i <= n; i++)
        mp[i][i] = 0;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = mp[v][u] = min(mp[v][u], w);
    }
    int t = prim();
    if (t == INF) puts("impossible");
    else cout << t;
    return 0;
}