hdu 1301 Jungle Roads

 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\n",sum);
56     }
57     return 0;
58 }