Prim算法：经过图中所有节点的最短路径

题目链接：53. 寻宝（第七期模拟笔试）

#include<bits/stdc++.h>
using namespace std;// v为节点数量，e为边数量
int v, e;// 最小生成树
void prim(vector<vector<int>>& adj) {vector<int> dist(v+1, INT_MAX); // 节点到生成树的距离，初始化为最大距离vector<int> used(v+1, 0); // 是否已经加入到生成树中，0表示没加入，1表示加入vector<int> pre_node(v+1, 0); // 生成树中节点i的前驱节点，0表示没有前驱// 把序号为1的节点加入生成树，在生成树中的节点到生成树的距离为0dist[1] = 0; for (int i = 1; i <= v; ++i) {// 找到生成树距离最小的节点加入生成树int closest_node_idx = -1;for (int j = 1; j <= v; ++j) {if (!used[j] && (closest_node_idx == -1 ||  dist[j] < dist[closest_node_idx]) ) {closest_node_idx = j;}}used[closest_node_idx] = 1;// 更新节点到生成树的距离并保存其前驱节点，方便最后计算最短路径for (int k = 1; k <= v; ++k) {if (!used[k] && dist[k] > adj[closest_node_idx][k] ) {dist[k] = adj[closest_node_idx][k];pre_node[k] = closest_node_idx;}}}int res = 0;// 从编号为2的节点开始算最短路径，因为第1个节点没有前驱节点（没有向前的边）for (int i = 2; i <= v; ++i) {res += adj[i][pre_node[i]];}printf("%d\n", res);}int main() {while (cin>>v>>e) {int v1, v2, val;std::vector<vector<int>> adj(v+1, vector<int>(v+1, INT_MAX));for (int i = 0; i < e; i++) {scanf("%d%d%d", &v1, &v2, &val);adj[v1][v2] = val;adj[v2][v1] = val;}prim(adj);}return 0;
}