acwing858 Prim算法求最小生成树（模板）

res记录最小生成树的边权和，st[] 记录该点是否在集合内，初始化dist[] 记录该点到集合最近距离
st记录随机一个点到集合，（一般是1）
for 更新所有点到"集合"最短距离
for n-1次
    for 循环点，找到集合外距离"集合"最近的点t
    st记录t加入集合
    res加上t的最短距离dist[t]
    if （最短的距离dist[t]为INF ）return INF 说明不是连通图，无最小生成树
    for 更新"集合"外的点到集合距离
return res

#include <bits/stdc++.h>

using namespace std;

int n,m,a,b,c;
const int N=505;
int g[N][N],dist[N];
bool st[N];//状态，是否在集合里 

int prim(){
	int res=0;
	memset(dist,0x3f,sizeof dist);
	st[1]=true;
	for(int i=2;i<=n;i++) dist[i]=min(dist[i],g[1][i]);
	for(int i=0;i<n-1;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
		}
		st[t]=true;
		res+=dist[t];
		if(dist[t]>0x3f3f3f3f/2) return dist[t];
		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--){
		scanf("%d%d%d",&a,&b,&c);
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	int ans=prim();
	if(ans>0x3f3f3f3f/2) puts("impossible");
	else printf("%d\n",ans);
	return 0;
}

int prim(){
	int res=0;
	memset(dist,0x3f,sizeof dist);
	for(int i=0;i<n;i++){//集合初始为空的情况也考虑进
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
		}
		st[t]=true;
		if(i) res+=dist[t];
		if(i&&dist[t]>0x3f3f3f3f/2) return dist[t];
		for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
	}
	return res;
}