题目描述
直接明了代码有详细注释
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int g[N][N];
int dist[N];
bool st[N];
int res;
int n,m;
void add(int a,int b,int c){g[a][b]=min(g[a][b],c);}
void prim(){
dist[1]=0;
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;//确定这个点
res+=dist[t];把确定的所有距离加起来
if(dist[t]==0x3f3f3f3f){cout<<"impossible"; return ;}
for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);//更新不在最小生成树的点到最短生成树的距离为下一步确定一个最小点做准备
}
cout<<res;
return ;
}
int main(){
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
prim();
}