C++实现【问题描述】Prim算法解决的是带权重的无向图上连接所有顶点的耗费最小的生成树。Q使用最小堆数据结构。 【输入形式】在屏幕上输入顶点个数和连接顶点间的边的权矩阵。 【输出形式】第1个顶点为起始点，顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。 【样例1输入】 8 0 15 7 0 0 0 0 10 15 0 0 0 0 0 0 0 7 0 0 9 12 5 0 0 0 0 9 0 0 0 0 0 0 0 12 0 0 6 0 0 0 0 5 0 6 0 14 8 0 0 0 0 0 14 0 3 10 0 0 0 0 8 3 0 【样例1输出】 3 1 7 6 3 5 5 6 6 8 6 8 7 8 3 4 3 9 2 1 15 【样例说明】 输入：顶点个数为8。连接顶点间边的权矩阵大小为8行8列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。 输出：第1个顶点为起始点，顺序输出按照贪心选择得到的各顶点序号，及该顶点的前驱顶点序号，及路径长度。

以下是C++实现Prim算法的代码，使用最小堆数据结构：

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

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

int n; // 顶点个数
int g[MAXN][MAXN]; // 边的权重矩阵
int dist[MAXN]; // 存储每个节点到已选中节点的最小距离
int pre[MAXN]; // 存储每个节点的前驱节点
bool vis[MAXN]; // 标记每个节点是否已经被选中

struct Node {
    int u, dist;
    bool operator<(const Node& rhs) const {
        return dist > rhs.dist; // 最小堆，按照距离从小到大排序
    }
};

void prim() {
    priority_queue<Node> pq;
    pq.push({0, 0}); // 从节点0开始
    dist[0] = 0;

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

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

        for (int v = 0; v < n; ++v) {
            if (!vis[v] && g[u][v] < INF && g[u][v] < dist[v]) {
                dist[v] = g[u][v];
                pre[v] = u;
                pq.push({v, dist[v]});
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 0) g[i][j] = INF;
        }
        dist[i] = INF;
    }

    prim();

    for (int i = 1; i < n; ++i) {
        cout << i + 1 << " " << pre[i] + 1 << " " << dist[i] << endl;
    }

    return 0;
}

说明：

1. 输入格式为顶点个数和连接顶点间的边的权矩阵，其中0表示两个顶点间没有边连接。
2. 初始化距离矩阵`dist`为无穷大，表示所有节点到已选中节点的距离都未知。
3. 使用最小堆来存储节点和其到已选中节点的最小距离。
4. 每次从最小堆中取出距离最小的节点，标记为已选中，更新其他节点到已选中节点的最小距离。
5. 输出每个节点的序号、前驱节点序号和路径长度。注意节点序号从1开始，需要加1输出。