比赛 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.