cowtour.pas

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

{
ID:maigoak1
PROG:cowtour
}

program cowtour;
const
  maxn=150;
  infinity=maxlongint;
type
  coord=record
    x,y:longint;
  end;
var
  fin,fout:text;
  v:array[1..maxn]of coord;
  p:array[1..maxn,1..maxn]of real;{Shortest paths}
  longest:array[1..maxn]of real;
  diameter:array[1..maxn]of real;
  n,i,j:byte;
  min,len:real;
  c:char;
function dist(a,b:byte):real;
  begin
    dist:=sqrt(power(v[a].x-v[b].x,2)+power(v[a].y-v[b].y,2));
  end;
procedure floyd;
  var
    i,j,k:byte;
    len:real;
  begin
    for k:=1 to n do
      for i:=1 to n do
        for j:=1 to n do begin
          len:=p[i,k]+p[k,j];
          if len<p[i,j] then p[i,j]:=len;
        end;
  end;
begin
  assign(fin,'cowtour.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do
    readln(fin,v[i].x,v[i].y);
  for i:=1 to n do begin
    for j:=1 to n do begin
      read(fin,c);
      if i=j then
        p[i,j]:=0
      else if c='1' then
        p[i,j]:=dist(i,j)
      else
        p[i,j]:=infinity;
    end;
    readln(fin);
  end;
  close(fin);

  floyd;

  fillchar(longest,sizeof(longest),0);
  for i:=1 to n do
    for j:=1 to n do
      if p[i,j]<infinity then if p[i,j]>longest[i] then longest[i]:=p[i,j];

  fillchar(diameter,sizeof(diameter),0);
  for i:=1 to n do
    for j:=1 to n do
      if p[i,j]<infinity then if longest[j]>diameter[i] then diameter[i]:=longest[j];

  min:=infinity;
  for i:=1 to n do
    for j:=1 to n do
      if p[i,j]=infinity then begin
        len:=longest[i]+longest[j]+dist(i,j);
        if diameter[i]>len then len:=diameter[i];
        if diameter[j]>len then len:=diameter[j];
        if len<min then min:=len;
      end;

  assign(fout,'cowtour.out');
  rewrite(fout);
  writeln(fout,min:0:6);
  close(fout);
end.