AcWing 858. Prim算法求最小生成树（稠密图）

题目链接

https://www.acwing.com/problem/content/description/860/

思路

prim算法的思想就是，我们维护一个最优集合，然后寻找所有不在集合的点连向集合的最短边，然后将这个点加入集合，并将权值加入总权值中，对于每一个最短边的点，我们用该点更新一下其他点到集合的距离就好了（这里和迪杰斯特拉不太一样，迪杰斯特拉是更新下一个点到源点的距离，而这里是更新没在集合中的点到集合的距离）

代码

#include
using namespace std;

const int N = 500+10;

int n,m;
int g[N][N];
int dis[N];
int vis[N];
const int INF = 0x3f3f3f3f;

int prim(){
    memset(dis,0x3f,sizeof dis);
    int ans = 0;
    for(int i = 0;i