比赛 |
noip20081103 |
评测结果 |
AWWTTTTTTA |
题目名称 |
放养奶牛 |
最终得分 |
20 |
用户昵称 |
MayLava |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-03 21:58:44 |
显示代码纯文本
program MayLava;
type
rec=record
x,y:integer;
end;
var
scv:array[0..1,1..40]of real;
past:array[0..1,1..40,-100..100,-100..100]of boolean;
site:array[1..100,1..40]of rec;
num:array[1..100]of integer;
n:longint;
procedure start;
var
f:text;
i,j:longint;
begin
assign(f,'cowties.in');
reset(f);
readln(f,n);
for i:=1 to n do begin
read(f,num[i]);
for j:=1 to num[i] do
read(f,site[i,j].x,site[i,j].y);
readln(f);
end;
close(f);
fillchar(scv,sizeof(scv),0);
fillchar(past,sizeof(past),true);
end;
procedure main;
var
temp:array[1..40]of real;
min:real;
i,j,k,l,ti:longint;
begin
for i:=2 to n do begin
for j:=1 to num[i] do begin
for k:=1 to num[i-1] do
if past[(i-1) mod 2,k,site[i,j].x,site[i,j].y] then
temp[k]:=scv[(i-1) mod 2,k]+sqrt(sqr(site[i-1,k].x-site[i,j].x)+sqr(site[i-1,k].y-site[i,j].y));
min:=10*maxlongint;
for k:=1 to num[i-1] do
if (temp[k]>0) and (temp[k]<min) then begin
min:=temp[k];
ti:=k;
end;
scv[i mod 2,j]:=min;
for k:=-100 to 100 do
for l:=-100 to 100 do
past[i mod 2,j,k,l]:=past[(i-1) mod 2,ti,k,l];
past[i mod 2,j,site[i,j].x,site[i,j].y]:=false;
end;
end;
for j:=1 to num[1] do begin
for k:=1 to num[n] do
if past[n mod 2,k,site[1,j].x,site[1,j].y] then
temp[k]:=scv[n mod 2,k]+sqrt(sqr(site[n,k].x-site[1,j].x)+sqr(site[n,k].y-site[1,j].y));
min:=10*maxlongint;
for k:=1 to num[n] do
if (temp[k]>0) and (temp[k]<min) then begin
min:=temp[k];
ti:=k;
end;
scv[(n+1) mod 2,j]:=min;
for k:=-100 to 100 do
for l:=-100 to 100 do
past[(n+1) mod 2,j,k,l]:=past[n mod 2,ti,k,l];
past[(n+1) mod 2,j,site[1,j].x,site[1,j].y]:=false;
end;
end;
procedure print;
var
f:text;
min:real;
i:longint;
begin
assign(f,'cowties.out');
rewrite(f);
min:=10*maxlongint;
for i:=1 to num[1] do
if (scv[(n+1) mod 2,i]>0) and (scv[(n+1) mod 2,i]<min) then min:=scv[(n+1) mod 2,i];
writeln(f,trunc(min*100));
close(f);
end;
BEGIN
start;
main;
print;
END.