POJ1251

#include
#include
#include<string.h>
#include
#include
#define maxn 110
#define INF 1000000
using namespace std;
int n;
int Edge[maxn][maxn];
int path[maxn];
int vis[maxn];
int sum = 0;
void prime(int u0)
{
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        path[i] = Edge[u0][i];
    }
    vis[u0] = 1;
    sum = 0;
    for(int i=1; i<=n; i++)
    {
        int tt,mmin = INF;
        for(int j=1; j<=n; j++)
        {
            if(vis[j] == 0 && path[j] < mmin)
            {
                mmin = path[j];
                tt = j;
            }
        }
        if(mmin == INF) break;
        sum += path[tt];
        vis[tt] = 1;
        for(int k=1; k<=n; k++)
        {
            if(vis[k] == 0 && path[k] > Edge[tt][k])
            {
                path[k] = Edge[tt][k];
            }
        }
    }
    printf("%d\n",sum);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
    while(~scanf("%d",&n))
    {
        if(n == 0) break;
        char ch,ch1;
        int u,v;
        int w,Q;
        memset(Edge,INF,sizeof(Edge));
        memset(path,INF,sizeof(path));
        for(int i=1; i)
        {
            cin>>ch1>>Q;
            u = ch1 - 64;
            for(int j=1; j<=Q; j++)
            {
                cin>>ch1>>w;
                v = ch1 - 64;
                Edge[u][v] = w;
                Edge[v][u] = w;
            }
        }
        prime(1);
    }
    return 0;
}