比赛 noip20081103 评测结果 AATTTTTTTA
题目名称 放养奶牛 最终得分 30
用户昵称 zxc111 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-03 21:29:31
显示代码纯文本
program ooo;
var
i,j,k,n,m,l,aa,ss:longint;
min:extended;
a:array[1..100] of longint;
x,y:array[1..100,-100..100] of longint;
f:array[-100..100,-100..100] of boolean;
t:text;
procedure oo(l,r:longint;q:extended);
var
i,j,k:longint;
begin
if q>min then exit;
if l=n then
 if q+sqrt(sqr(x[l,r]-x[1,aa])+sqr(y[l,r]-y[1,aa]))<min
  then
   begin min:=q+sqrt(sqr(x[l+1,r]-x[l,aa])+sqr(y[l,r]-y[1,aa]));
  exit;end else exit;
for i:=1 to a[l+1] do
 if f[x[l+1,i],y[l+1,i]]=false
  then
   begin
    f[x[l+1,i],y[l+1,i]]:=true;
    oo(l+1,i,q+sqrt(sqr(x[l+1,i]-x[l,r])+sqr(y[l+1,i]-y[l,r])));
    f[x[l+1,i],y[l+1,i]]:=false;
   end;
  end;
begin
assign(t,'cowties.in');
reset(t);
readln(t,n);
for i:=1 to n do
 begin
  read(t,a[i]);
  for j:=1 to a[i]*2 do
   begin
   k:=j+2;
    read(t,m);
    if k mod 2=0 then y[i,j div 2]:=m else x[i,k div 2]:=m;
   end;
  readln(t);
 end;
close(t);
fillchar(f,sizeof(f),false);
min:=maxlongint;
for i:=1 to a[1] do
 begin
  aa:=i;
  f[x[1,i],y[1,i]]:=true;
  oo(1,i,0);
  f[x[1,i],y[1,i]]:=false;
 end;
 assign(t,'cowties.out');
 rewrite(t);
write(t,trunc(min*100));
close(t);
end.