比赛 |
20091110 |
评测结果 |
MMMMMMMMMM |
题目名称 |
高速公路 |
最终得分 |
0 |
用户昵称 |
EnAsn |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2009-11-10 12:00:49 |
显示代码纯文本
program ex;
type
ss=array[-3000..3000,-3000..3000]of longint;
sz=array[1..200,1..200]of real;
zs=array[1..200,1..4]of integer;
var
f:ss;
map:sz;
n,am,t,m:integer;
v:integer;
procedure init;
var
i,j:integer;
x1,y1,x2,y2:integer;
begin
assign(input,'highway.in');
assign(output,'highway.out');
reset(input);
rewrite(output);
readln(m);
readln(x1,y1,x2,y2);
f[x1,y1]:=1;f[x2,y2]:=2;
map[1,2]:=sqrt(sqr(x1-x2)+sqr(y1-y2));
map[2,1]:=map[1,2];
t:=2;
for i:=2 to m do
begin
readln(x1,y1,x2,y2);
if f[x1,y1]<>0 then
begin
if f[x2,y2]<>0 then
begin
map[f[x1,y1],f[x2,y2]]:=sqrt(sqr(x1-x2)+sqr(y1-y2));
map[f[x2,y2],f[x1,y1]]:=map[f[x1,y1],f[x2,y2]];
end
else begin
inc(t);f[x2,y2]:=t;
map[f[x1,y1],t]:=sqrt(sqr(x1-x2)+sqr(y1-y2));
map[t,f[x1,y1]]:=map[t,f[x1,y1]];
end;
end
else begin
inc(t);f[x1,y1]:=t;
if f[x2,y2]<>0 then
begin
map[t,f[x2,y2]]:=sqrt(sqr(x1-x2)+sqr(y1-y2));
map[f[x2,y2],t]:=map[t,f[x2,y2]];
end
else begin
map[t,t+1]:=sqrt(sqr(x1-x2)+sqr(y1-y2));
map[t+1,t]:=map[t,t+1];
inc(t);f[x2,y2]:=t;
end;
end;
am:=f[x2,y2];
end;
for i:=1 to m do
for j:=1 to m do
if map[i,j]=0 then map[i,j]:=maxint;
readln(v);
close(input);
end;
procedure dijk;
var
i,j:integer;
num:integer;
min:real;
flag:array[1..200]of boolean;
begin
fillchar(flag,sizeof(flag),true);
flag[1]:=false;
num:=1;
for i:=2 to t do
begin
min:=999999999;
for j:=2 to t do
if (map[1,j]<min)and(flag[j]) then
begin
min:=map[1,j];
num:=j;
end;
flag[num]:=false;
for j:=2 to t do
if (j<>num)and(map[1,num]+map[num,j]<map[1,j])and(flag[j]) then
map[1,j]:=map[1,num]+map[num,j];
end;
writeln(map[1,am]/v:0:2);
close(output);
end;
begin
init;
dijk;
end.