#include<stdio.h>
#define MAX 0xfffffff
#define MaxVertex 21
//prim求最小支持樹(shù)，多用于求邊稠密網(wǎng)的最小支持樹(shù) 時(shí)間復(fù)雜度O(n*n)n為頂點(diǎn)數(shù);
#define  vertextype int
int n;
bool s[MaxVertex];//該點(diǎn)是否被訪問(wèn)
vertextype cost[MaxVertex];
vertextype dist[MaxVertex][MaxVertex];
void Init()
{
 int i,j,a,b,c;
  scanf("%d",&n);//先輸入點(diǎn)個(gè)數(shù)
    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表示邊輸入結(jié)束
     dist[a][b]=dist[b][a]=c;
    s[1]=true;//該點(diǎn)已經(jīng)被訪問(wèn)
    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，因?yà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]))//可能出現(xiàn)已經(jīng)訪問(wèn)過(guò)的點(diǎn)cost[k]保持原值，但這沒(méi)有關(guān)系，以為在上面的處理步驟(1)中不對(duì)這些邊處理
  //dist[j][j]<cost[k]的比較則是為了重判集合V到V-U集合的點(diǎn)的距離，注意是整個(gè)集合V到各個(gè)未納入V的點(diǎn)的距離！
   cost[k]=dist[j][k];
  }
}
 printf("%d\n",best);
 return 0;
}
學(xué)以致用 joj 1170