比赛 HAOI2009 模拟试题3 评测结果 AEEEEEEEEE
题目名称 公路修建 最终得分 10
用户昵称 wo shi 刘畅 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2012-06-28 16:52:39
显示代码纯文本
const
  oo=100000000000000;

var
  v:Array[0..100000]of boolean;
  n,i,j,p,time:longint;
  x,y:array[0..5000]of longint;
  f:Array[0..100000]of double;

  ans,min:double;

function dis(i,j:longint):double;
begin
  if i=j then dis:=oo
  else dis:=sqrt(sqr(y[i]-y[j])+sqr(x[i]-x[j]));
end;

begin
  assign(input,'roadz.in'); reset(input);
  assign(output,'roadz.out'); rewrite(output);
  readln(n);
  for i:=1 to n do read(x[i],y[i]);

  for i:=1 to n do
  f[i]:=dis(1,i);

  min:=oo;
  v[1]:=true;
  for i:=1 to n do
  if dis(1,i)<min then
  begin
    p:=i;
    min:=dis(1,i);
  end;
  v[p]:=true;
  ans:=ans+min;

  for time:=1 to n-2 do
  begin
    for i:=1 to n do
    if (not v[i])and(dis(p,i)<f[i]) then
      f[i]:=dis(p,i);

    min:=maxlongint;
    for i:=1 to n do
    if (f[i]<min)and(not v[i]) then
    begin
      p:=i;
      min:=f[i];
    end;
    v[p]:=true;
    ans:=ans+min;
  end;
  writeln(ans:0:2);
  close(input);
  close(output);
end.