#include<stdio.h>
#define MAX 0xfffffff
#define MaxVertex 21
//prim求最小支持树，多用于求边稠密网的最小支持树 时间复杂度O(n*n)n为顶点数;
#define  vertextype int
int n;
bool s[MaxVertex];//该点是否被访问
vertextype cost[MaxVertex];
vertextype dist[MaxVertex][MaxVertex];
void Init()
{
 int i,j,a,b,c;
  scanf("%d",&n);//先输入点个数
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      dist[i][j]=MAX;
    while(scanf("%d%d%d",&a,&b,&c),a||b||c)//0 0 0表示边输入结束
     dist[a][b]=dist[b][a]=c;
    s[1]=true;//该点已经被访问
    for(i=2;i<=n;i++)
    {
     cost[i]=dist[1][i];
     s[i]=false;//初始化为false
    }
}
int main()
{
 freopen("s.txt","r",stdin);
 freopen("key.txt","w",stdout); 
int i,j,k,m,a,b,c,best,min;
    best=0;
 Init();
for(i=1;i<n;i++)//i不能等于n，因为n-1条边
{
 min=MAX;
 j=1;
 for(k=2;k<=n;k++)
  if(cost[k]<min&&(!s[k]))//  (1)
  {
   min=cost[k];
   j=k;
  }
  s[j]=true;
  best+=min;
  for(k=2;k<=n;k++)
  {
   if(dist[j][k]<cost[k]&&(!s[k]))//可能出现已经访问过的点cost[k]保持原值，但这没有关系，以为在上面的处理步骤(1)中不对这些边处理
  //dist[j][j]<cost[k]的比较则是为了重判集合V到V-U集合的点的距离，注意是整个集合V到各个未纳入V的点的距离！
   cost[k]=dist[j][k];
  }
}
 printf("%d\n",best);
 return 0;
}
学以致用 joj 1170