学步园

//poj1251 先用prime做 后面还要用Kruskal算法来做 
#include <iostream>
#define inf 101
using namespace std;
int vertex[28];
int weight[28][28];
int dist[28];
bool mark[28];
int sum;
int prime(int n)
{
	dist[0] = 0;
	mark[0] = true;
	//初始化距离表 
	for(int i = 1; i < n; i++)
	{
		dist[i] = weight[0][i];
	} 
 	for(int i = 1; i < n; i++)
	{
		//寻找距离党组织最近的点 
		int min1 = inf;
		int minIndex = -1;
		for(int j = 1; j < n; j++)
		{
			if(!mark[j] && dist[j] < min1)
			{
				min1 = dist[j];
				minIndex = j;
			}
		}
		//加入党组织，更新距离表 
		sum += dist[minIndex];
		dist[minIndex] = 0;
		mark[minIndex] = true;
		for(int j = 1; j < n; j++)
		{
			if(!mark[j])
				dist[j] = (weight[minIndex][j] < dist[j])?weight[minIndex][j]:dist[j];
		}
	}
	return sum;
}
int main()
{
	int n;
	cin>>n;
	char a,c;
	int edgeNum;
	int weight1;
	while(n)
	{
		memset(vertex, 0, sizeof(vertex));
		memset(dist, inf, sizeof(dist));
		memset(mark, 0, sizeof(mark));
		memset(weight, inf, sizeof(weight));
		for(int i = 0; i < n; i++)
			weight[i][i] = 0;
		for(int i = 0; i < n -1 ; i++)
		{
			cin>>a;
			cin>>edgeNum;
			for(int j = 0; j < edgeNum; j++)
			{
				cin>>c;
				cin>>weight1;
				int k = int(c - 'A');
				weight[i][k] = weight1;
				weight[k][i] = weight1;
			}
		}
		sum = 0;
		cout<<prime(n)<<endl;
		cin>>n;
	}
	return 0;	
}