最小生成樹。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1251
#include <stdio.h>
#include <stdlib.h>

const int LEN  = 1000;

typedef struct
{
    int b;
    int e;
    int length;
}type;
type seg[LEN];
int next;


void init ()
{

    next = 0;
}

int point[LEN];

void make ( int n )
{

    for ( int i=0; i<n; i++ )
    {
        point[i] = -1;
    }
}

int find ( int a )
{

    if ( point[a] < 0 )
    {
        return a;
    }
    int r = find ( point[a] );
    point[a] = r;

    return r;
}

void un ( int a, int b )
{

    int ra = find ( a );
    int rb = find ( b );

    if ( point[ra] < point[rb] )
    {
        point[ra] += point[rb];
        point[rb] = ra;
    }
    else
    {
        point[rb] += point[ra];
        point[ra] = rb;
    }
}

int cmp ( const void *a, const void *b )
{

    return ( ( type * )a )->length - ( ( type * )b )->length;
}

int kul ( int n )
{

    int ans = 0;

    qsort ( seg, next, sizeof ( type ), cmp );
    make ( n );
    for ( int i=0; i< next; i++ )
    {
        if ( find ( seg[i].b ) != find ( seg[i].e ) )
        {
            ans += seg[i].length;
            un ( seg[i].b, seg[i].e );
        }
    }

    return ans;
}

int main ()
{

    int n;
    char chi[5], chj[5];
    int len;
    int in;

    while ( scanf ( "%d", &n ) != EOF && n )
    {
        init ();
        for ( int i=0; i<n-1; i++ )
        {
            scanf ( "%s%d", &chi, &len );
            for ( int j=0; j<len; j++ )
            {
                scanf ( "%s%d", &chj, &in );
                seg[next].b = chi[0] - 'A';
                seg[next].e = chj[0] - 'A';
                seg[next++].length = in;
            }
        }

        printf ( "%d\n", kul ( n ) );
    }
    return 0;
}