比赛 |
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.