比赛 HAOI2009 模拟试题3 评测结果 AAAAAAAATT
题目名称 公路修建 最终得分 80
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2009-04-23 10:21:21
显示代码纯文本
program day3_2;
  const
    maxn=5000;
    Inf=100000000;
  var
       n:       longint;
       ans:     real;
       x,y:     array[1..maxn] of real;
       cost:    array[1..maxn,1..maxn] of real;
       dist:    array[1..maxn] of real;
       mark:    array[1..maxn] of boolean;


  function dis(a,b:longint):real;
     var
         result :real;
    begin
      result :=sqrt( sqr(x[a]-x[b]) + sqr(y[a]-y[b]) );
      exit(result);
    end;

  procedure Init;
    var
         i,j:   longint;
    begin
      readln(n);
      for i :=1 to n do readln(x[i],y[i]);
      for i :=1 to n do
          for j :=1 to n do cost[i,j] :=dis(i,j);
    end;

  procedure Main;
    var
        i,j,k:    longint;
        min:    real;

    begin
      for i :=1 to n do dist[i] :=Inf; dist[1] :=0;
      for i :=1 to n do begin
          min :=Inf;
          for j :=1 to n do  if (not mark[j]) and (dist[j]<min)
              then begin min :=dist[j]; k :=j; end;
          ans :=ans+dist[k]; mark[k] :=true;
          for j :=1 to n do if cost[k,j] <dist[j]
              then dist[j] :=cost[k,j];
          end;
      writeln(ans:0:2);
    end;


  begin
    assign(input,'roadz.in'); reset(input);
    assign(output,'roadz.out'); rewrite(output);
    Init;
    Main;
    close(input); close(output);
  end.