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