prim(普里姆)

#include<iostream>
#include<cstring>
using namespace std;const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];//存邻接矩阵
int dist[N];//存储其他点到当前最小生成树的距离
bool vis[N];//存最点是否在最小生成树中
int n, m;int prim()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;//初始化int res = 0;//最小生成树的最小距离for (int i = 0; i < n; i++)//n个点{int t = -1;for (int j = 1; j <= n; j++){if (!vis[j] && (t == -1 || dist[t] > dist[j]))//寻找边权最小的点{t = j;}}if (t == -1)break;//t == -1 所有点都已经加入最小生成树 可退出循环res += dist[t];//更新最小生成树的距离vis[t] = true;//将点加入最小生成树for (int j = 1; j <= n; j++){dist[j] = min(dist[j], g[t][j]);//更新从最小的点到他相邻的点的最小距离}}return res;
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);//初始化邻接矩阵while (m--){int x, y, w;cin >> x >> y >> w;g[x][y] = g[y][x] = min(g[x][y], w);}int t = prim();cout << t;return 0;
}