pku1251.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#define TheMax 100000000
int dis[27][27];
int mindis[27];
int N;

void init()
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		dis[i][i] = 0;
		for (j = i + 1; j < N; j++)
		{
			dis[j][i] = dis[i][j] = TheMax;
		}
	}
}

int prim()
{
	int i, j, u;
	int uu[27];
	int min, sum;
	
	for (i = 1; i < N; i++)
	{
		mindis[i] = dis[0][i];
		uu[i] = 0;
	}
	uu[0] = 1;
	sum = 0;

	for (j = 0; j < N - 1; j++)
	{
		min = TheMax;
		u = -1;
		for (i = 0; i < N; i++)
		{
			if (!uu[i] && mindis[i] < min)
			{
				min = mindis[i];
				u = i;
			}
		}
		uu[u] = 1;
		sum += min;
		for (i = 0; i < N; i++)
		{
			if (!uu[i] && mindis[i] > dis[i][u])
			{
				mindis[i] = dis[i][u];
			}
		}
	}
	return sum;
}

int main()
{
	int i, j, p, d;
	char c0, c1;
	while (scanf("%d\n", &N) != -1 && N)
	{
		init();
		for (j = 0; j < N - 1; j++)
		{
			scanf("%c %d ", &c0, &p);
			for (i = 0; i < p; i++)
			{
				scanf("%c %d ", &c1, &d);
				dis[c1 - 'A'][c0 - 'A'] = dis[c0 - 'A'][c1 - 'A'] = d;
			}
			scanf("\n");
		}
		printf("%d\n", prim());
	}
	return 0;
}