朴素的prim，还是自己写的用着习惯
pku 1251
#include<stdio.h>
#include<string.h>
#define N 30
#define M 1<<27
int g[N][N],n; //g[][]的初值为M, 下标从0开始
int prim()
{
int i,j,k,ans=0;
int dis[N], visit[N], pre[N];
for(i=0; i<n; i++){
dis[i]=g[0][i];
visit[i]=0;
pre[i]=0;
}
visit[0]=1;
for(i=1; i<n; i++){
int mn=M, v=0;
for(j=0; j<n; j++)
if(!visit[j] && dis[j]<mn){
mn=dis[j];
v=j;
}
if(v==0) break;
visit[v]=1;
ans+=mn;
for(j=0; j<n; j++)
if(!visit[j] && dis[j]>g[v][j]){
dis[j]=g[v][j];
pre[j]=v;
}
}
return ans;
}
int main()
{
int i,j,k,p,q,z;
char s[5];
while(scanf("%d", &n) && n){
for(i=0; i<n; i++)
for(j=0; j<n; j++)
g[i][j]=M;
for(i=0; i<n-1; i++){
scanf("%s %d", s, &k);
p=s[0]-'A';
for(j=0; j<k; j++){
scanf("%s %d", s, &z);
q=s[0]-'A';
g[p][q]=g[q][p]=z;
}
}
printf("%d\n", prim());
}
return 0;
}