比赛 20110318 评测结果 AAAAAATTTT
题目名称 公路修建 最终得分 60
用户昵称 ybh 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-03-18 20:38:34
显示代码纯文本
program roadz;
var
  x,y:array[0..5001] of int64;
  low:array[0..5001] of double;
  n,i,j,k:longint;
  sum,min:double;

function a(i,j:longint):double;
begin
  a:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;

begin
  assign(input,'roadz.in');
  reset(input);
  assign(output,'roadz.out');
  rewrite(output);

  readln(n);
  for i:=1 to n do
    readln(x[i],y[i]);

  for i:=2 to n do
    low[i]:=a(1,i);
  low[1]:=-1;
  sum:=0;
  for i:=1 to n-1 do
  begin
    min:=-10;
    for j:=1 to n do
      if (low[j]>-1) and ((low[j]<min) or (min=-10)) then
        begin
          min:=low[j];
          k:=j
        end;
    sum:=sum+min;
    low[k]:=-1;
    for j:=1 to n do
      if a(k,j)<low[j]
        then low[j]:=a(k,j)
  end;

  writeln(sum:0:2);
  close(input);
  close(output);
end.