AcWing题目链接
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=510,INF=0x3f3f3f; int n,m; bool st[N];//状态 int g[N][N]; //创建图 int d[N];//点之间对距离 int prim(){ memset(d,0x3f,sizeof d); int res=0; d[1] = 0; for(int i=0;i<n;i++) { int u =-1, MIN = INF; for(int j=1;j<=n;j++) //循环寻找最小点 { if(!st[j] && d[j] < MIN){ u=j; MIN = d[j]; } } if(u==-1)return INF;//如果不连通 st[u] = true; res += d[u]; for(int j=1;j<=n;j++){ if(!st[j] && g[u][j]!=INF && g[u][j] < d[j]) d[j] = g[u][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 t=prim(); if(t==INF)cout<<"impossible"<<endl; else cout<<t<<endl; return 0; }