代码随想录算法【Day57】

53. 寻宝

Prim算法 是求解加权无向图最小生成树的经典算法。其基本思想是：从图中任意一个节点出发，逐步扩展生成树，每次选择连接树与非树的最小权边。直到所有节点都被加入生成树中，算法结束。

#include<iostream>
#include<vector>
#include <climits>
​
using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;}vector<int> minDist(v + 1, 10001);vector<bool> isInTree(v + 1, false);for (int i = 1; i < v; i++) {int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}int result = 0;for (int i = 2; i <= v; i++) {result += minDist[i];}cout << result << endl;
}