比赛 HAOI2009 模拟试题3 评测结果 AEEEEEEEEE
题目名称 公路修建 最终得分 10
用户昵称 LXYXYNT 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2009-04-23 10:22:34
显示代码纯文本
const
  inf='roadz.in';
  ouf='roadz.out';
  maxn=5000;
  maxm=400*5000;

type
  node=record
         data:extended;
         next,k:longint;
       end;

var
  a:array[0..maxn,1..2] of longint;
  first:array[0..maxn] of longint;
  d:array[0..maxn] of extended;
  e:array[1..maxm*2] of node;
  flag:array[0..maxn] of boolean;
  k,nn,r,p,q,o,i,j,m,n:longint;
  pp,ans:extended;

function edg(p,q:longint):extended;
begin
  exit(sqrt(sqr(a[p,1]-a[q,1])+sqr(a[p,2]-a[q,2])));
end;

procedure addedge(p,q:longint;o:extended);
begin
  inc(nn);
  e[nn].k:=p;
  e[nn].data:=o;
  e[nn].next:=first[q];
  first[q]:=nn;
end;

begin
  assign(input,inf);reset(input);
  assign(output,ouf);rewrite(output);
  r:=0;
  nn:=0;
  readln(n);
  for i:=1 to n do readln(a[i,1],a[i,2]);

  for i:=1 to n do
   for j:=1 to n do
    if i<>j then
    begin
      pp:=edg(i,j);
      addedge(i,j,pp);
      addedge(j,i,pp);
    end;

  for i:=0 to n do d[i]:=999999999;
  d[1]:=0;

  i:=first[1];
  while i<>0 do
  begin
    if e[i].data<d[e[i].k] then d[e[i].k]:=e[i].data;
    i:=e[i].next;
  end;

  fillchar(flag,sizeof(flag),false);
  flag[1]:=true;

  for p:=1 to n-1 do
  begin
    k:=0;
    for j:=1 to n do
     if (d[j]<d[k]) and not flag[j] then k:=j;

    ans:=ans+d[k];
    flag[k]:=true;

    i:=first[k];
    while i<>0 do
    begin
      if e[i].data<d[e[i].k] then d[e[i].k]:=e[i].data;
      i:=e[i].next;
    end;
  end;
  writeln(ans:0:2);
  close(input);
  close(output);
end.