comehome.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 59 行

{
ID:maigoak1
PROG:comehome
}

program comehome;
var
  fin,fout:text;
  cost:array[1..52,1..52]of integer;
  dist:array[1..52]of longint;
  s:set of 1..52;
  p,c,n1,n2,newadd,i,j:integer;
  mincost:longint;
  v1,v2,junk:char;
function let2num(l:char):integer;
  begin
    if l<'a' then let2num:=ord(l)-64 else let2num:=ord(l)-70;
  end;
begin
  for i:=1 to 52 do
    for j:=1 to 52 do
      cost[i,j]:=maxint;
  assign(fin,'comehome.in');
  reset(fin);
  readln(fin,p);
  for i:=1 to p do begin
    readln(fin,v1,junk,v2,junk,c);
    n1:=let2num(v1);n2:=let2num(v2);
    if c<cost[n1,n2] then begin cost[n1,n2]:=c;cost[n2,n1]:=c;end;
  end;

  for i:=1 to 52 do
    dist[i]:=maxlongint;
  s:=[26];
  dist[26]:=0;
  newadd:=26;
  repeat
    for i:=1 to 52 do
      if not (i in s) then
        if cost[newadd,i]<maxint then
          if dist[newadd]+cost[newadd,i]<dist[i] then
            dist[i]:=dist[newadd]+cost[newadd,i];
    mincost:=maxint;
    for i:=1 to 52 do
      if not (i in s) then
        if dist[i]<mincost then begin
          mincost:=dist[i];
          newadd:=i;
        end;
    s:=s+[newadd];
    dist[newadd]:=mincost;
  until newadd<26;

  assign(fout,'comehome.out');
  rewrite(fout);
  writeln(fout,chr(64+newadd),' ',mincost);
  close(fout);
end.