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