比赛 20110318 评测结果 AEEEEEEEEE
题目名称 公路修建 最终得分 10
用户昵称 wo shi 刘畅 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-03-18 20:13:28
显示代码纯文本
const
  oo=9999999999;

var
  n,i,j,p,time:longint;
  total,min,t:real;
  x,y:Array[0..10000]of longint;
  f:array[0..10000]of boolean;
  d:array[0..10000]of real;

function dis(i,j:longint):real;
begin
  dis:=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:=1 to n do d[i]:=oo;

  for i:=1 to n do f[i]:=false;

  d[1]:=0;

  total:=0;

  for time:=1 to n do
  begin

    min:=oo;
    for i:=1 to n do
    if not f[i] then
      if d[i]<min then
      begin
        p:=i;
        min:=d[i];
      end;

    total:=total+min;

    f[p]:=true;
    for i:=1 to n do
    begin
      t:=dis(p,i);
      if (not f[i])and(t<d[i]) then
      d[i]:=t;
    end;

  end;

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