记录编号	231668	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2016-02-27 12:11:55	内存使用	0.36 MiB

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#define transfer(x) (x<='Z'&&x>='A')?(x-'A'+27):(x-'a'+1)
using namespace std;
struct edge{
	int to,next,w;
}lst[20050];
int len=1;
int first[60];//1-26:a-z 27-52:A-Z
void insert(int a,int b,int w){
	lst[len].to=b;
	lst[len].next=first[a];
	lst[len].w=w;
	first[a]=len;
	len++;
}
int dis[60];
bool vis[60];
struct node{
	int to,w;	
	node(int _to,int _w){
		to=_to;w=_w;
	}
	bool operator < (const node &a)const{
		return w>a.w;
	}
};
void djs(int s){
	dis[s]=0;
	priority_queue<node> q;
	q.push(node(s,0));
	while(!q.empty()){
		while(vis[q.top().to]&&!q.empty())q.pop();
		if(q.empty())break;
		int v=q.top().to,cost=q.top().w;
		q.pop();
		vis[v]=true;
		for(int pt=first[v];pt;pt=lst[pt].next){
			if(dis[lst[pt].to]>cost+lst[pt].w){
				dis[lst[pt].to]=cost+lst[pt].w;
				q.push(node(lst[pt].to,cost+lst[pt].w));
			}
		}
	}
}
char readch(){
	char ch;
	while(ch=getchar(),!isalpha(ch));
	return ch;
}
int main(){
	freopen("comehome.in","r",stdin);
	freopen("comehome.out","w",stdout);
	int m;scanf("%d",&m);
	char ch1,ch2;int cost;
	while(m--){
		ch1=readch();ch2=readch();
		scanf("%d",&cost);
		ch1=transfer(ch1);
		ch2=transfer(ch2);
		insert(ch1,ch2,cost);
		insert(ch2,ch1,cost);
	}
	memset(dis,63,sizeof(dis));
	djs(52);
	int ans=1<<25;int mark;
	for(int i=27;i<52;++i){
		if(dis[i]<ans){
			mark=i;
			ans=dis[i];
		}
	}
	printf("%c %d\n",'A'+mark-27,ans);
	fclose(stdin);fclose(stdout);
	return 0;
}