比赛 noip20081103 评测结果 AWWWWWWAWA
题目名称 放养奶牛 最终得分 30
用户昵称 thegy 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-03 20:18:36
显示代码纯文本
program cowties;
type
  location=record
             x,y:longint;
           end;
var
  a:array[1..100]of longint;
  b:array[1..100,1..40]of location;
  f:array[1..100,1..40]of real;
  v:array[1..100,1..40]of boolean;
  i,j,n:longint;
  ans,ans0:real;
  fin,fout:text;
function min(x,y:real):real;
begin
  if x<y then min:=x else min:=y;
end;
procedure jyhss(x,y:longint);
var
  iii:longint;
begin
  if x=1 then exit;
  if x=2 then begin
    f[2,y]:=sqrt(sqr(b[1,i].x-b[2,y].x)+sqr(b[1,i].y-b[2,y].y));
    v[2,y]:=true;
  end else begin
        f[x,y]:=99999999;
        for iii:=1 to a[x-1] do begin
          if not(v[x-1,iii]) then jyhss(x-1,iii);
          f[x,y]:=min(f[x,y],f[x-1,iii]+sqrt(sqr(b[x-1,iii].x-b[x,y].x)+sqr(b[x-1,iii].y-b[x,y].y)));
        end;
        v[x,y]:=true;
      end;
end;
procedure main;
var
  ii,jj:longint;
  t:real;
begin
  for ii:=1 to n do
    for jj:=1 to a[i] do
      v[ii,jj]:=false;
  ans0:=9999999;
  for ii:=1 to a[n] do begin
    jyhss(n,ii);
    t:=sqrt(sqr(b[n,ii].x-b[1,i].x)+sqr(b[n,ii].y-b[1,i].y));
    if f[n,ii]+t<ans0 then ans0:=f[n,ii]+t;
  end;
end;
begin
  assign(fin,'cowties.in'); reset(fin);
  assign(fout,'cowties.out'); rewrite(fout);
  read(fin,n);
  for i:=1 to n do begin
    read(fin,a[i]);
    for j:=1 to a[i] do read(fin,b[i,j].x,b[i,j].y);
  end;
  ans:=9999999;
  for i:=1 to a[1] do begin
    main;
    if ans0<ans then ans:=ans0;
  end;
  writeln(fout,trunc(ans*100));
  close(fin);
  close(fout);
end.