Description
Input
Output
Sample Input
9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0
Sample Output
216 30
利用primie算法实现，基本模板就可以：
#include<stdio.h>
#include<string.h>
int e[100][100];
int n;
int inf=99999;
void init();
int prime();
int main()
{
int cur,m,i,j,temp;
char str[100];
while(scanf("%d",&n)&&n)
{
init();
for(i=1;i<n;i++)
{
scanf("%s",str);
cur=str[0]-64;
scanf("%d",&m);
for(j=1;j<=m;j++)
{
scanf("%s",str);
temp=str[0]-64;
scanf("%d",&e[cur][temp]);
e[temp][cur]=e[cur][temp];
}
}
printf("%d\n",prime());
}
return 0;
}
int prime()
{
int sum=0;
int book[100]={0};
int dis[100]={0},i,min,minx,j;
for(i=1;i<=n;i++)
dis[i]=e[1][i];
book[1]=1;
for(j=1;j<n;j++)
{
min=inf;
for(i=1;i<=n;i++)
{
if(min>=dis[i]&&book[i]==0)
{
min=dis[i];
minx=i;
}
}
book[minx]=1;
if(min!=inf) sum+=min;
for(i=1;i<=n;i++)
{
if(book[i]==0&&dis[i]>e[minx][i])
dis[i]=e[minx][i];
}
}
return sum;
}
void init()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
}
}
原文：http://blog.csdn.net/chudongfang2015/article/details/51346864