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

program roads;
var
map:array[1..1000,1..1000] of real;
i,j,k,m,n,v0:longint;
ans:double;
x,y:array[1..1000] of real;
procedure prim;
var
lowcost:array[1..4000] of real;
i,j,k:longint;   min:real;
begin
 for i:=1 to n do begin
    lowcost[i]:=map[v0,i];
    end;
   for i:=1 to n-1 do
    begin
     min:=maxlongint;
     for j:=1 to n do
     if (lowcost[j]<min)and(lowcost[j]<>-1) then begin
      min:=lowcost[j]; k:=j;
      end;
      ans:=ans+lowcost[k];
      lowcost[k]:=0;
    for j:=1 to n do
     if map[k,j]<lowcost[j] then  begin
     lowcost[j]:=map[k,j];
     end;
    end;
   end;
begin
assign(input,'roads.in');reset(input);
assign(output,'roads.out');rewrite(output);
readln(n,m);
for i:=1 to n do
 readln(x[i],y[i]);
for i:=1 to n do
 for j:=1 to n do map[i,j]:=-1;
for i:=1 to n-1 do
 for j:=i+1 to n do
 begin
 map[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
 map[j,i]:=map[i,j];
 end;
 for i:=1 to m do
 begin
 readln(j,k);
 map[j,k]:=0;
 map[k,j]:=0;
 end;
 v0:=1;
prim;
writeln(ans:0:2);
close(output);
end.