AcWing 1140. Shortest network (minimum spanning tree)

AcWing 1140. The shortest network
Minimum spanning tree template

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

int dist[N];  //dist It records the distance between this point and the connected block 
int n, m;
int w[N][N];
bool st[N];

int prime(){
    
	int res = 0;
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;  // Only the number in the initialized connected block is 1 The point of  
	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 It records the distance between this point and the connected block , here t Is the outermost point in the connected block  
		}
	}
	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;
}