http://acm.hdu.edu.cn/showproblem.php?pid=1301
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 500 5 using namespace std; 6 const int inf=1<<30; 7 8 int g[maxn][maxn]; 9 int dis[maxn]; 10 bool vis[maxn]; 11 int n,x,mm,sum; 12 char ch,ch1; 13 14 void prim() 15 { 16 memset(vis,false,sizeof(vis)); 17 for(int i=0; i<n; i++) dis[i]=g[0][i]; 18 dis[0]=0; 19 vis[0]=true; 20 for(int i=1; i<n; i++) 21 { 22 int m=inf,x; 23 for(int y=0; y<n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y]; 24 vis[x]=true; 25 sum+=m; 26 for(int y=0; y<n; y++) if(!vis[y]&&dis[y]>g[x][y]) dis[y]=g[x][y]; 27 } 28 } 29 30 int main() 31 { 32 while(scanf("%d",&n)!=EOF) 33 { 34 if(n==0) break; 35 getchar(); 36 for(int i=0; i<27; i++) 37 { 38 for(int j=0; j<27; j++) 39 { 40 if(i==j) g[i][j]=0; 41 else g[i][j]=inf; 42 } 43 } 44 for(int i=1; i<=n-1; i++) 45 { 46 scanf("%c %d%*c",&ch,&x); 47 for(int j=0; j<x; j++) 48 { 49 scanf("%c %d%*c",&ch1,&mm); 50 g[ch-'A'][ch1-'A']=g[ch1-'A'][ch-'A']=mm; 51 } 52 } 53 sum=0; 54 prim(); 55 printf("%d ",sum); 56 } 57 return 0; 58 }