最小生成树prim

 最小生成树（三）Prim算法及存储结构_哔哩哔哩_bilibili⁤

311 最小生成树 Prim 算法_哔哩哔哩_bilibili

#include <iostream>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;#define ll unsigned long long
#define INF 0x7fffffff
typedef pair<int, int> PII;
struct Node {int v, w;
};
vector<Node> edge[6];
int dis[6], vis[6] = { 0 }, wsum = 0;void prim(int s) {for (int i = 0; i < 6; i++) dis[i] = INF;dis[s] = 0;priority_queue<PII> q; //{点与圈内的距离， 点}q.push({ 0, s });while (!q.empty()) {int x = q.top().second; q.pop();if (vis[x]) continue;vis[x] = 1;wsum += dis[x];for (auto a : edge[x]) {int v = a.v, w = a.w;if (dis[v] > w) {dis[v] = w;q.push({ -dis[v], v });}}}return;
}int main() {edge[0].push_back({ 1, 6 }), edge[1].push_back({ 0, 6 });edge[0].push_back({ 2, 1 }), edge[2].push_back({ 0, 1 });edge[0].push_back({ 3, 5 }), edge[3].push_back({ 0, 5 });edge[1].push_back({ 2, 5 }), edge[2].push_back({ 1, 5 });edge[1].push_back({ 4, 3 }), edge[4].push_back({ 1, 3 });edge[2].push_back({ 3, 5 }), edge[3].push_back({ 2, 5 });edge[2].push_back({ 4, 6 }), edge[4].push_back({ 2, 6 });edge[2].push_back({ 5, 4 }), edge[5].push_back({ 2, 4 });edge[3].push_back({ 5, 2 }), edge[5].push_back({ 3, 2 });edge[4].push_back({ 5, 6 }), edge[5].push_back({ 4, 6 });prim(0);cout << wsum;return 0;
}