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

program roads;
var
        a:array[1..1000,1..1000]of double;
        data:array[1..2,1..1000]of int64;
        m,n,i,j:longint;
        x,y:int64;
        mincost:array[1..1001]of double;
        closed:array[1..1001]of int64;
function dist(x1,y1,x2,y2:int64):double;
begin
        exit(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
end;
procedure init;
var
        dd:double;
begin
        assign(input,'roads.in');
        reset(input);
        assign(output,'roads.out');
        rewrite(output);
        readln(n,m);
        for i:=1 to n do
        for j:=1 to n do
        if i<>j then
        a[i,j]:=maxlongint else a[i,j]:=0;
        for i:=1 to n do
        begin
        readln(data[1,i],data[2,i]);
        end;
        for i:=1 to n-1 do
         for j:=i+1 to n do if i<>j then
         begin
         a[i,j]:=dist(data[1,i],data[2,i],data[1,j],data[2,j]);
         a[j,i]:=a[i,j];
         end;
         for i:=1 to m do
         begin
                readln(x,y);
                a[x,y]:=0;
                a[y,x]:=0;
         end;
end;
procedure closef;
begin
        close(input);
        close(output);
end;
procedure main;
var
        i,j,p:longint;
        min,ans:double;
        v:array[1..1000]of boolean;
begin
        fillchar(v,sizeof(v),0);
        v[1]:=true;
        for i:=1 to n do
        begin
        closed[i]:=1;
        mincost[i]:=a[1,i];
        end;
        for i:=2 to n do
        begin
                min:=maxlongint;
                for j:=1 to n do if
                not(v[j])and(min>mincost[j]) then
                begin
                        min:=mincost[j];
                        p:=j;
                end;
                v[p]:=true;
                for j:=1 to n do  if not(v[j]) then
                 if mincost[j]>a[p,j] then
                 begin
                        mincost[j]:=a[p,j];
                        closed[j]:=p;
                 end;
        end;
        ans:=0;
        for i:=1 to n do
        ans:=ans+a[i,closed[i]];
        writeln(ans:0:2);
end;
begin
        init;
        main;
        closef;
end.