比赛 20091111 评测结果 AAAAAAAAAA
题目名称 建造路径 最终得分 100
用户昵称 .Xmz 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2009-11-11 09:01:13
显示代码纯文本
program xzm;
var
f1,f2:text;
f:array[1..1000,1..1000]of double;
d:array[1..1000]of double;
x,y:array[1..1000]of int64;
yy:array[1..1000]of boolean;
max,s:double;
a,b,t1,t2,m,n,c:longint;
begin
 assign(f1,'roads.in');assign(f2,'roads.out');
 reset(f1);rewrite(f2);
  read(f1,n,m);
  for a:=1 to n do
   read(f1,x[a],y[a]);
  for a:=1 to n do
   for b:=a+1 to n do
    begin
     f[a,b]:=maxlongint;
    end;
  for a:=1 to n do
   for b:=a+1 to n do
    begin
    f[a,b]:=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
    f[b,a]:=f[a,b];
    end;
  for a:=1 to m do
   begin
   read(f1,t1,t2);
   f[t1,t2]:=0;
   f[t2,t1]:=0;
   end;
  for a:=1 to n do
   d[a]:=maxlongint;
  c:=1;
  repeat
   yy[c]:=true;
   for a:=1 to n do
   if (not yy[a]) then
   if f[c,a]<d[a] then d[a]:=f[c,a];
   max:=maxlongint;
   for a:=1 to n do
    if (max>d[a])and(not yy[a]) then begin max:=d[a];c:=a;end;
   if max<>maxlongint then s:=s+max;
  until max=maxlongint;
  writeln(f2,s:0:2);
 close(f1);close(f2);
end.