记录编号	21791	评测结果	AAAAAAAAAA
题目名称	最小密度路径	最终得分	100
用户昵称	ZHZH	是否通过	通过
代码语言	Pascal	运行时间	1.470 s
提交时间	2010-11-15 15:24:18	内存使用	0.62 MiB

program path;
var
  n,m:longint;
  f:array[0..50,0..50,0..50] of longint;
  v1,v2:text;
procedure init;
 var
 i,j,k,l:longint;
  begin
  readln(v1,n,m);
  fillchar(f,sizeof(f),255);
  for i:=1 to m do
  begin
  readln(v1,j,k,l);
  if (f[1,j,k]=-1) or (l<f[1,j,k]) then f[1,j,k]:=l;
  end;

  for i:=1 to n do f[0,i,i]:=0;
   for l:=2 to n do
    for k:=1 to n do
     for i:=1 to n do
      for j:=1 to n do
       if (f[l-1,i,k]>-1) and (f[1,k,j]>-1)
        and ((f[l,i,j]=-1) or (f[l-1,i,k]+f[1,k,j]<f[l,i,j])) then
         f[l,i,j]:=f[l-1,i,k]+f[1,k,j]
  end;

procedure work;
  var
    i,j,l:longint;
    ans:real;
  begin
    readln(v1,m);
    for m:=1 to m do
      begin
        readln(v1,i,j);
        ans:=maxlongint;
        for l:=0 to n do
          if (f[l,i,j]<>-1) and (f[l,i,j]/l<ans) then ans:=f[l,i,j]/l;
          if ans<>maxlongint then writeln(v2,ans:0:3)
                           else writeln(v2,'OMG!');
      end;
  end;

begin
  assign(v1,'path.in'); reset(v1);
  assign(v2,'path.out'); rewrite(v2);
  init;
  work;
  close(v1); close(v2);
end.