比赛 |
HAOI2009 模拟试题3 |
评测结果 |
AEEEEEEEEE |
题目名称 |
公路修建 |
最终得分 |
10 |
用户昵称 |
LXYXYNT |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2009-04-23 10:22:34 |
显示代码纯文本
const
inf='roadz.in';
ouf='roadz.out';
maxn=5000;
maxm=400*5000;
type
node=record
data:extended;
next,k:longint;
end;
var
a:array[0..maxn,1..2] of longint;
first:array[0..maxn] of longint;
d:array[0..maxn] of extended;
e:array[1..maxm*2] of node;
flag:array[0..maxn] of boolean;
k,nn,r,p,q,o,i,j,m,n:longint;
pp,ans:extended;
function edg(p,q:longint):extended;
begin
exit(sqrt(sqr(a[p,1]-a[q,1])+sqr(a[p,2]-a[q,2])));
end;
procedure addedge(p,q:longint;o:extended);
begin
inc(nn);
e[nn].k:=p;
e[nn].data:=o;
e[nn].next:=first[q];
first[q]:=nn;
end;
begin
assign(input,inf);reset(input);
assign(output,ouf);rewrite(output);
r:=0;
nn:=0;
readln(n);
for i:=1 to n do readln(a[i,1],a[i,2]);
for i:=1 to n do
for j:=1 to n do
if i<>j then
begin
pp:=edg(i,j);
addedge(i,j,pp);
addedge(j,i,pp);
end;
for i:=0 to n do d[i]:=999999999;
d[1]:=0;
i:=first[1];
while i<>0 do
begin
if e[i].data<d[e[i].k] then d[e[i].k]:=e[i].data;
i:=e[i].next;
end;
fillchar(flag,sizeof(flag),false);
flag[1]:=true;
for p:=1 to n-1 do
begin
k:=0;
for j:=1 to n do
if (d[j]<d[k]) and not flag[j] then k:=j;
ans:=ans+d[k];
flag[k]:=true;
i:=first[k];
while i<>0 do
begin
if e[i].data<d[e[i].k] then d[e[i].k]:=e[i].data;
i:=e[i].next;
end;
end;
writeln(ans:0:2);
close(input);
close(output);
end.