AcWing 1140. 最短网络 （最小生成树）

AcWing 1140. 最短网络
最小生成树模板

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int dist[N];  //dist记录的是这个点距离连通块的距离
int n, m;
int w[N][N];
bool st[N];

int prime(){
    
	int res = 0;
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;  //初始化连通块内只有编号为1的点 
	for(int i = 1; i <= n; i ++ ){
    
		int t = -1;
		for(int j = 1; j <= n; j ++ ){
    
			if(!st[j] && (t == -1 || dist[t] > dist[j])){
    
				t = j;
			}
		}
		res += dist[t];
		st[t] = true;
		
		for(int j = 1; j <= n; j ++ ){
    
			dist[j] = min(dist[j], w[t][j]);  //dist记录的是这个点距离连通块的距离，此时t是连通块内最靠外的点 
		}
	}
	return res;
}

int main()
{
    
	cin>>n;
	for(int i = 1; i <= n; i ++ ){
    
		for(int j = 1; j <= n; j ++ ){
    
			cin>>w[i][j];
		}
	}
	cout<<prime()<<endl;
	return 0;
}