记录编号	15301	评测结果	AAAAAAAAAA
题目名称	151.[USACO Dec07] 建造路径	最终得分	100
用户昵称	chengyang	是否通过	通过
代码语言	Pascal	运行时间	0.212 s
提交时间	2009-11-11 15:39:32	内存使用	7.80 MiB

program roads;
var
  map:array[0..1001,0..1001]of real;
  f:array[0..1001]of boolean;
  v:array[0..1001]of real;
  a:array[0..1001,1..2]of real;
  q,n,m,i,j,k,l:longint;
  min:double;
begin
  assign(input,'roads.in');
  assign(output,'roads.out');
  reset(input); rewrite(output);
  readln(n,m);
  fillchar(v,sizeof(v),0);
  fillchar(f,sizeof(f),0);
  fillchar(a,sizeof(a),0);
  for i:=1 to n+1 do begin
    for j:=1 to n+1 do map[i,j]:=999999999;
  end;
  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
    map[i,j]:=sqrt(sqr(a[i,1]-a[j,1])+sqr(a[i,2]-a[j,2]));

  for i:=1 to m do begin
    readln(j,k);
    map[j,k]:=0; map[k,j]:=0;
  end;

  for i:=1 to n do
   begin
    v[i]:=9999999999;
    map[i,i]:=0;
   end;
  v[1]:=0;
  fillchar(f,sizeof(f),true);
  f[1]:=false;
  q:=1;
  for i:=1 to n-1 do begin
    min:=99999999999;
    for j:=1 to n do
      if (f[j])and(v[j]>map[q,j]) then v[j]:=map[q,j];

    for j:=1 to n do
     if f[j]and(v[j]<min) then
      begin
       min:=v[j];
       k:=j;
      end;
    f[k]:=false;
    q:=k;
  end;
  min:=0;
  for i:=1 to n do min:=min+v[i];
  writeln(min:0:2);
  close(input); close(output);
end.