题目链接
AC代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int p,r;
const int N = 55;
int g[N][N];
int dist[N];
int st[N];
int prime()
{
memset(dist, 0x3f,sizeof dist);
memset(st,0, sizeof st);
int res = 0;
for(int i=0; i<p; i++)
{
int t = -1;
for(int j=1; j<=p; j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j])) t = j;
}
if(i&&dist[t]==INF) return INF;
if(i) res+=dist[t];
st[t] = 1;
for(int j=1; j<=p; j++)
{
dist[j] = min(dist[j],g[t][j]);
}
}
return res;
}
int main(){
while(~scanf("%d",&p)&&p)
{
memset(g,0x3f, sizeof g);
scanf("%d",&r);
if(r==0)
{
puts("0");
continue;
}
for(int i=0; i<r; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u][v] = g[v][u] = min(g[u][v],w);
}
printf("%d\n",prime());
}
return 0;
}