#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