记录编号	341871	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	citrono	是否通过	通过
代码语言	Pascal	运行时间	0.018 s
提交时间	2016-11-07 21:51:20	内存使用	0.16 MiB

var
  a:array['A'..'z','A'..'z']of longint;
  tt,i,j,n,ans,min:longint;
  k,c,c2,c1:char;
  d:array['A'..'z']of longint;
  f:array['A'..'z']of boolean;
begin
  assign(input,'comehome.in');reset(input);
  assign(output,'comehome.out');rewrite(output);
  fillchar(a,sizeof(a),$7f div 2);
  fillchar(d,sizeof(d),$7f div 2);
  fillchar(f,sizeof(f),false);
  readln(n);
  for i:=1 to n do
    begin
      read(c1,c,c2);
      read(tt);
      if (tt<a[c1,c2])or(tt<a[c2,c1])
         then begin a[c1,c2]:=tt;a[c2,c1]:=a[c1,c2];end;
      readln;
    end;
  for c:='A' to 'z' do
    if a[c,'Z']<10000 then d[c]:=a[c,'Z'];
  d['Z']:=0;
  f['Z']:=true;
  for i:=2 TO n do
       begin
         k:='0';
         min:=10000000;
         for c1:='A' TO 'z' do
           if (c1<>'Z')and(d[c1]<min)and(not f[c1]) then
              begin
                k:=c1;min:=d[c1];
              end;
         if (min=maxlongint)or(k='0') then break;
         f[k]:=true;
         for c2:='A' TO 'z' do
            if (d[c2]>d[k]+a[k,c2])and(not f[c2])
                then d[c2]:=d[k]+a[k,c2];
       end;
  min:=maxlongint;
  for c:='A' to 'z' do
    if (c in ['A'..'Y'])and(d[c]<min) then
      begin
         k:=c;min:=d[c];
      end;
  writeln(k,' ',min);
  close(input);
 close(output);
end.