记录编号	50612	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2012-11-26 20:15:22	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
using namespace std;
void floyd(int leng[101][101],int n){
	int i,j,k;
	for(k=0;k<n;k++){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(leng[i][k]+leng[k][j]<leng[i][j]) leng[i][j]=leng[i][k]+leng[k][j];
			}
		}
	}
}
int main(){
	freopen("comehome.in","r",stdin);
	freopen("comehome.out","w",stdout);
	int leng[101][101]={0},p,i,j,x,ans=26;
	char a,b;
	for(i=0;i<70;i++){
		for(j=0;j<70;j++){
			if(j==i) continue;
			leng[i][j]=99999999;
		}
	}
	scanf("%d",&p);
	for(i=0;i<p;i++){
		cin>>a>>b>>x;
		if('a'<=a&&a<='z') a-='a';
		else a-='A',a+=26;
		if('a'<=b&&b<='z') b-='a';
		else b-='A',b+=26;
		if(leng[a][b]>x) leng[a][b]=x,leng[b][a]=x;
	}
	floyd(leng,52);
	for(i=26;i<51;i++){
		if(leng[i][51]<leng[ans][51]) ans=i;
	}
	a=char('A'+ans-26);
	cout<<a<<" "<<leng[ans][51]<<endl;
	return 0;
}