记录编号	15317	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	王瑞祥K	是否通过	通过
代码语言	Pascal	运行时间	0.667 s
提交时间	2009-11-11 16:51:46	内存使用	7.76 MiB

program roads(input,output);
var
 map:array[1..1000,1..1000]of double;
 use:array[1..1000]of boolean;
 f:array[1..1000,1..2]of int64;
 low:array[1..1000]of double;
 i,j,k,x,y,m,n:longint;
 min,ans:double;
begin
 assign(input,'roads.in');assign(output,'roads.out');
 reset(input);rewrite(output);
 readln(n,m);
 for i:=1 to n do readln(f[i,1],f[i,2]);
 for i:=1 to n do
  for j:=1 to n do
   map[i,j]:=sqrt(sqr(f[i,1]-f[j,1])+sqr(f[i,2]-f[j,2]));
 for i:=1 to m do begin
  readln(x,y);
  map[x,y]:=0; map[y,x]:=0;
 end;
 fillchar(use,sizeof(use),true);
 for i:=1 to n do low[i]:=map[1,i];
 ans:=0;
 use[1]:=false;
 for i:=1 to n-1 do begin
  min:=10e20;
  for j:=1 to n do
   if (low[j]<min) and use[j] then begin
    min:=low[j];
    k:=j;
   end;
  ans:=ans+min;
  use[k]:=false;
  for j:=1 to n do
   if map[k,j]<low[j] then low[j]:=map[k,j];
 end;
 writeln(ans:0:2);
 close(input);close(output);
end.