比赛 20110318 评测结果 AEEEEEEEEE
题目名称 公路修建 最终得分 10
用户昵称 绝对零度 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-03-18 20:30:58
显示代码纯文本
program roadz;
type aaa=record
     x,y:longint;
    end;
var a:array[1..5000] of aaa;
i,j,k,n,x,y:longint;
m:real;
procedure prim(v0:integer);

var
   lowcost,closest:array[1..5000] of real;
   i,j,k:integer;  min,ans:real;
begin
   for i:=1 to n do begin
      lowcost[i]:=sqrt(sqr(a[v0].x-a[i].x)+sqr(a[v0].y-a[i].y));
      closest[i]:=v0;
   end;
   for i:=1 to n-1 do begin
      min:=maxint;
      for j:=1 to n do
         if (lowcost[j]<min) and (lowcost[j]<>0) then begin
            min:=lowcost[j];
            k:=j;
         end;
      ans:=ans+ lowcost[k];
      lowcost[k]:=0;
      for j:=1 to n do
         if sqrt(sqr(a[j].x-a[k].x)+sqr(a[j].y-a[k].y))<lowcost[j] then begin
            lowcost[j]:=sqrt(sqr(a[j].x-a[k].x)+sqr(a[j].y-a[k].y));
            closest[j]:=k;
         end;
   end;
 m:=ans;
end;
begin
 assign(input,'roadz.in');
 reset(input);
 assign(output,'roadz.out');
 rewrite(output);
 readln(n);
 m:=0;
 for i:=1 to n do
  begin
   readln(x,y);
   a[i].x:=x;a[i].y:=y;
  end;
   prim(1) ;
  writeln(m:0:2);

 close(input);
 close(output);
end.