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

var
  n,m:longint;
  f:array[0..50,0..50,0..50] of longint;

procedure init;
  var
    i,j,k,l:longint;
  begin
    readln(n,m);
    fillchar(f,sizeof(f),255);
    for i:=1 to m do
      begin
        readln(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(m);
    for m:=1 to m do
      begin
        readln(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(ans:0:3)
                           else writeln('OMG!');
      end;
  end;

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