比赛 |
noip20081103 |
评测结果 |
AAWWWWWWWW |
题目名称 |
放养奶牛 |
最终得分 |
20 |
用户昵称 |
francis |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-03 22:08:28 |
显示代码纯文本
program cowties;
const
fin='cowties.in';
fou='cowties.out';
max=10000000000;
var
f:array[1..40,1..100,1..40]of real;
a:array[1..100,1..40,1..2]of longint;
b:array[-100..100,-100..100]of boolean;
c:array[1..100,1..2]of longint;
s:array[1..100]of longint;
p,k,i,j,n:longint;
all,min:real;
f1,f2:text;
procedure init1;
begin
for i:=1 to n do
begin
read(f1,s[i]);
for j:=1 to s[i] do
read(f1,a[i,j,1],a[i,j,2]);
end;
min:=3000000000000;
end;
procedure print;
begin
all:=all+sqrt(sqr(c[n,1]-c[1,1])+sqr(c[n,2]-c[1,2]));
if min>all then min:=all;
end;
procedure dfs(k:longint);
var
x,y,i,j:longint;
xall:real;
begin
for i:=1 to s[k] do
begin
x:=a[k,i,1]; y:=a[k,i,2];
if b[x,y]=false then
begin
xall:=all;
if k=1 then all:=0
else all:=all+sqrt(sqr(c[k-1,1]-x)+sqr(c[k-1,2]-y));
if all>min then exit;
b[x,y]:=true; c[k,1]:=x; c[k,2]:=y;
if k=n then print else dfs(k+1);
b[x,y]:=false;
all:=xall;
end;
end;
end;
procedure init2;
begin
for i:=1 to n do
begin
read(f1,s[i]);
for j:=1 to s[i] do
read(f1,a[i,j,1],a[i,j,2]);
end;
for k:=1 to s[1] do
for i:=2 to n do
for j:=1 to s[i] do
f[k,i,j]:=max;
end;
procedure p1;
begin
init1;
dfs(1);
min:=min*100;
write(f2,min:0:0);
close(f1); close(f2);
end;
procedure print2;
begin
min:=max;
for i:=1 to s[1] do
for j:=1 to s[n] do
begin
all:=f[i,n,j]+sqrt(sqr(a[1,i,1]-a[n,j,1])+sqr(a[1,i,2]-a[n,j,2]));
if all<min then min:=all;
end;
min:=min*100;
write(f2,min:0:0);
close(f1); close(f2);
end;
procedure p2;
begin
init2;
for k:=1 to s[1] do
for i:=2 to n do
for j:=1 to s[i] do
begin
for p:=1 to s[i-1] do
begin
all:=sqrt(sqr(a[i-1,p,1]-a[i,j,1])+sqr(a[i-1,p,2]-a[i,j,2]));
if f[k,i-1,p]+all<f[k,i,j] then f[k,i,j]:=f[k,i-1,p]+all;
end;
end;
print2;
end;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n);
if n<15 then p1 else p2;
end.