c++写一个邻接表的prim算法

以下是邻接表的Prim算法的实现：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> G[MAXN]; // 邻接表
int dist[MAXN]; // 到MST的最短距离
bool vis[MAXN]; // 是否已加入MST
int n, m;

struct Node { // 用于优先队列中的比较
    int u, d;
    Node(int u, int d) : u(u), d(d) {}
    bool operator<(const Node &rhs) const {
        return d > rhs.d;
    }
};

void Prim(int start) {
    memset(dist, INF, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[start] = 0;
    priority_queue<Node> pq;
    pq.push(Node(start, 0));

    while (!pq.empty()) {
        int u = pq.top().u;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].to;
            int w = G[u][i].weight;
            if (!vis[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(Node(v, dist[v]));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }

    Prim(1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) { // 无法到达
            cout << "No MST!" << endl;
            return 0;
        }
        ans += dist[i];
    }

    cout << "MST weight: " << ans << endl;

    return 0;
}

说明：

1. 首先我们定义了一个邻接表`G`，其中`G[i]`表示编号为`i`的点所连接的所有边。
2. 然后，我们定义了一个距离数组`dist`，表示每个点到MST的最短距离，初始时全部赋值为INF。
3. `vis`表示每个点是否已经被加入MST，初始时全部赋值为false。
4. 首先将起点加入MST，然后将起点的所有邻接点加入优先队列中，其中优先队列按照到MST的距离从小到大排序。
5. 从优先队列中取出距离MST最近的点u，并将其加入MST中。
6. 然后，遍历u的所有邻接点v，如果v未被加入MST且u到v的距离比目前v到MST的距离更短，则更新dist[v]的值，并将v加入优先队列。
7. 重复步骤5和6，直到所有点都被加入MST为止。
8. 最后遍历dist数组，如果有点无法到达MST，则说明无法构建MST，输出"No MST!"，否则输出MST的总权值。

时间复杂度：$O(m\log n)$，其中$m$为边数，$n$为点数。