4823385_ac_16ms_284k.cpp

部分PKU上的源码

#include<iostream>
#include<string>
#define maxl 999999999
using namespace std;
int map[30][30];
int x[30];
bool used[30];
int n;
int result;
char k[30];
void slove()
{
	int i,j;
	for(i=0;i<n;i++) x[i]=map[0][i];
	memset(used,false,sizeof(used));
	used[0]=true;
	for(i=0;i<n-1;i++)
	{
		int tmin=maxl,re=-1;
		for(j=0;j<n;j++)
		{
			if(x[j]<tmin&&used[j]==false)
			{
				tmin=x[j];
				re=j;
			}
		}
		result+=x[re];
		used[re]=true;
		for(j=0;j<n;j++)
		{
			if(map[re][j]<x[j]) x[j]=map[re][j];
		}
	}
}
int main()
{
	int i,j;
	while(cin>>n)
	{
		if(n==0) return 0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++) map[i][j]=maxl;
		for(i=0;i<n-1;i++)
		{
			int temp;
			cin>>k[i];
			cin>>temp;
			for(j=0;j<temp;j++)
			{
				char inin;
				int ttt;
				cin>>inin>>ttt;
				map[inin-'A'][i]=ttt;
				map[i][inin-'A']=ttt;
			}
		}
		result=0;
		slove();
		cout<<result<<endl;
	}
	return 0;
}