公路村村通 (30分)

#include<iostream>
#include<cstring>

#define maxn 1005
#define mm(a,x) memset(a,x,sizeof(a))
#define inf 0x3f3f3f3f

using namespace std;

int n,m;
int map[maxn][maxn];
int dist[maxn];
int vis[maxn];

int prim(){
   
	mm(dist,inf);
	dist[1]=0;
	int ans=0;
	for(int i=1;i<=n;i++){
   
		int u=-1,minn=inf;
		for(int j=1;j<=n;j++){
   
			if(!vis[j]&&dist[j]<minn){
   
				u=j;minn=dist[j];
			}
		}
		if(u==-1) break ;
		vis[u]=1; ans+=dist[u];
		for(int v=1;v<=n;v++){
   
			if(!vis[v]&&map[u][v]!=inf&&map[u][v]<dist[v]){
   
				dist[v]=map[u][v];
			}
		}
	}
	return ans;
}

int main(){
   
	cin>>n>>m;
	mm(map,inf);
	for(int i=1;i<=m;i++){
   
		int t1,t2,t3;cin>>t1>>t2>>t3;
		map[t1][t2]=map[t2][t1]=t3;
	}
	cout<<prim()<<endl;	
	return 0;
}```