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