记录编号	106730	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2014-06-18 18:05:58	内存使用	0.32 MiB

//题意明显，求map【x】【26】的最小值
#include<fstream>
using namespace std;
ifstream fin("comehome.in");
ofstream fout("comehome.out");
int map[60][60];
bool flag[100];
int a[100];//存有奶牛的牧场标号
const int INF=999999999;
int n;
int main()
{
	char ANS;
	int ans=INF;
	int counter=0;
	int i,j,k;
	char A,B;
	int DIS;
	int t,p;
	for(i=1;i<=59;i++)
		for(j=1;j<=59;j++)
		{
			if(i!=j)
			map[i][j]=INF;
		}
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>A>>B>>DIS;
		t=int(A)-64;
		p=int(B)-64;
		if(int(A)<96&&flag[t]==0&&int(A)!=90)
		{
			flag[t]=1;
			counter++;
			a[counter]=t;
		}
		if(int(B)<96&&flag[p]==0&&int(B)!=90)
		{
			flag[p]=1;
			counter++;
			a[counter]=p;
		}		
		if(DIS<map[t][p])
		{
		map[t][p]=DIS;
		map[p][t]=DIS;
		}
	}
	for(k=1;k<=59;k++)
		for(i=1;i<=59;i++)
			for(j=1;j<=59;j++)
				if(map[i][k]+map[k][j]<map[i][j])
					map[i][j]=map[i][k]+map[k][j];
	for(i=1;i<=counter;i++)
	{
		if(map[a[i]][26]<ans)
		{
			ans=map[a[i]][26];
			ANS=char(a[i]+64);
		}
	}
	fout<<ANS<<' '<<ans<<endl;
	return 0;
}