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

program bing;
type
 sb=record
 x,y:real;
end;
var
 f1,f2:text;
 n,m:integer;
 ans:real;
 a:array[1..1000] of sb;
 l:array[1..1000,1..1000] of real;
procedure init;
var
 i,j,c,d:integer;
begin
 assign(f1,'roads.in');reset(f1);
 assign(f2,'roads.out');rewrite(f2);
 readln(f1,n,m);
 for i:=1 to n do readln(f1,a[i].x,a[i].y);
 for i:=1 to n-1 do
  for j:=i+1 to n do
  begin
  l[i,j]:=sqrt((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y));
  l[j,i]:=l[i,j];
  end;
 for i:=1 to m do
 begin
  readln(f1,c,d);
  l[c,d]:=0;
  l[d,c]:=0;
 end;
end;
procedure prim;
var
 i,j,k:integer;
 ml:array[1..1000] of real;
 f:array[1..1000] of boolean;
 min:real;
begin
 fillchar(f,sizeof(f),true);
 f[1]:=false;
 for i:=1 to n do ml[i]:=l[1,i];
 for i:=1 to n-1 do
 begin
  min:=10000000;
  for j:=1 to n do
  if (ml[j]<min)and f[j] then
  begin
   min:=ml[j];
   k:=j;
  end;
  f[k]:=false;
  ans:=ans+ml[k];
  for j:=1 to n do
  if l[k,j]<ml[j] then
    ml[j]:=l[k,j];
  end;
end;
begin
 init;
 prim;
 writeln(f2,ans:0:2);
 close(f1);close(f2);
end.