#include <iostream>
#include <string.h>
using namespace std;
int road[100][100];
int dist[100];
bool visit[100];
char dic[]=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int position(char s)
{
	int pos;
	for(pos=1;;pos++)
		if(dic[pos]==s)
			return pos;
}
int main()
{
	int n,s,e,sum;
	char name;
	while(cin>>n&&n!=0)
	{
		memset(visit,0,sizeof(visit));
		int i,j,m,d;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			road[i][j]=10000;
			road[i][i]=0;
		}
			for(i=1;i<n;i++)
			{
				cin>>name>>m;
				s=position(name);
				while(m--)
				{
					cin>>name>>d;
					e=position(name);
					road[s][e]=d;
					road[e][s]=d;
				}
			}
			for(i=1;i<=n;i++)
			dist[i]=road[1][i];
            visit[1]=1;
			sum=0;
			for(i=1;i<n;i++)
			{
				int max=10000;
				int rec=-1;
				for(j=1;j<=n;j++)
					if(!visit[j]&&dist[j]<max)
					{
						max=dist[j];
						rec=j;
					}
					sum+=dist[rec];
					visit[rec]=1;
					for(j=1;j<=n;j++)
						if(!visit[j]&&road[rec][j]<dist[j])
							dist[j]=road[rec][j];
			}
			cout<<sum<<endl;
	}
	return 1;
}

	

• Re:oms！给力！prime算法就是好！ (8) Steven_Chen 2016-02-26 09:58:54
  • Re:oms！给力！prime算法就是好！ (27) xc19881023 2016-05-01 14:49:15