记录编号	190845	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.4]回家	最终得分	100
用户昵称	VacaTionGOD	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2015-10-04 21:43:27	内存使用	0.18 MiB

var
  p,n,kk,ii,min:longint;
  b,c,kg,i,j,k,ans:char;
  a:array['A'..'z','A'..'z'] of longint;
  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);
  for i:='A' to 'z' do
   for j:='A' to 'z' do
    if i=j then a[i,j]:=0 else a[i,j]:=maxlongint div 2;
  readln(p);
  for ii:=1 to p do
   begin
     readln(b,kg,c,kk);
      if kk<a[b,c] then begin
     a[b,c]:=kk;
     a[c,b]:=kk;        end;
   end;
   for i:='A' to 'z' do
    begin d[i]:=a['Z',i]; f[i]:=false; end;
   f['Z']:=true;
   for i:='A' to 'z' do
    begin
      min:=maxlongint; k:=' ';
      for j:='A' to 'z' do
       if (not f[j]) and (d[j]<min) then
        begin min:=d[j]; k:=j; end;
      if (k=' ') or (min=maxlongint) then break;
      f[k]:=true;
      for j:='A' to 'z' do
        if (not f[j]) and (d[k]+a[k,j]<d[j]) and (j<>'Z') then d[j]:=d[k]+a[k,j];
    end;
   min:=maxlongint div 2;
   for i:='A' to 'Y' do
    if d[i]<min then begin min:=d[i]; ans:=i; end;
  writeln(ans,' ',d[ans]);
close(input);
close(output);
end.