最小生成樹--prim算法

#include<bits/stdc++.h>
using namespace std;
const int N=5010,INF=0x3f3f3f3f;//正無窮
int n,m,dis[N],g[N][N],res;
bool st[N];
int prim() {
	memset(dis,0x3f,sizeof(dis));
	memset(st,0,sizeof(st));
	for(int i=0; i<n; i++) {
		int t=-1;
		for(int j=1; j<=n; j++) {
			if(!st[j]&&(t==-1||dis[t]>dis[j])) {
				t=j;
			}
		}
		if(i&&dis[t]==INF)//不存在最小生成樹
			return INF;
		if(i) {
			res+=dis[t];
		}
		st[t]=true;
		for(int j=1; j<=n; j++) {//更新距離 
			dis[j]=min(dis[j],g[t][j]);
		}
	}
	return res;
}
int main() {
	memset(g,0x3f,sizeof(g));//鄰接矩陣 初始化為無窮大 
	cin>>n>>m;
	while(m--) { //可能會有重邊
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	int ans=prim();
	if(ans!=INF){
		cout<<ans<<endl;
	}
}
           

輸入：

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
           

輸出：