比赛 noip20081103 评测结果 AAWWWWWWWA
题目名称 放养奶牛 最终得分 30
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-03 22:02:54
显示代码纯文本
program p2;
 var
     n:longint;
     ans:real;
     f:array[1..102,1..40] of real;
     s:array[1..102,0..80] of longint;

function dis(xx,yy,x,y:real):real;
 begin
  dis:=sqrt(sqr(xx-x)+sqr(yy-y));
 end;


procedure init;
 var
    i,j:longint;

 begin
  readln(N);
  for i:=1 to n do
    begin
    read(s[i,0]);
     for j:=1 to s[i,0]*2 do
     read(s[i,j]);
    end;
 end;

procedure main;
 var
     i,j,d1,d2:longint;
     tm,ans,x,y,xx,yy:real;

 begin
  inc(n); s[n]:=s[1];
  for i:=2 to n do
   for d1:=1 to s[i,0] do
    begin
     f[i,d1]:=maxlongint div 2;
     x:=s[i,d1*2-1]; y:=s[i,d1*2];
          j:=i-1;
          for d2:=1 to s[j,0] do
           begin
           xx:=s[j,d2*2-1]; yy:=s[j,d2*2];
           if (xx<>x) or (yy<>y)
           then
                begin
                tm:=f[j,d2]+dis(xx,yy,x,y);
                if tm<f[i,d1] then f[i,d1]:=tm;
                end;
           end;
     end;
  ans:=maxlongint;
  for i:=1 to s[n,0] do
  if f[n,i]<ans then ans:=f[n,i];
  writeln(trunc(ans*100));
 end;


begin
 assign(input,'cowties.in');
 assign(output,'cowties.out');
 reset(input); rewrite(output);
 init;
 main;
 close(input); close(output);
end.