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

program gls;
const maxint=-1;
var
m,n,a,b,w,k,i,j,q:longint;ans:real;
ss:array[0..50,0..50,0..50]of longint;

f,g:text;


begin
  assign(f,'path.in');reset(f);
  assign(g,'path.out');rewrite(g);
  readln(f,n,m);
  fillchar(ss,sizeof(ss),255);
  for k:=1 to m do
 begin readln(f,a,b,w);
    if (ss[1,a,b]=-1)or(w<ss[1,a,b])
    then ss[1,a,b]:=w;
 end;
 for i:=1 to n do ss[0,i,i]:=0;
 for w:=2 to n do
  for k:=1 to n do
   for i:=1 to n do
    for j:=1 to n do
    if (ss[w-1,i,k]>-1)and(ss[1,k,j]>-1)
        and((ss[w,i,j]=maxint)or(ss[w-1,i,k]+ss[1,k,j]<ss[w,i,j]))
        then ss[w,i,j]:=ss[w-1,i,k]+ss[1,k,j];

   readln(f,q);
  for k:=1 to q do
  begin readln(f,a,b);
      ans:=maxlongint;
     for i:=0 to n do
     if (ss[i,a,b]<>-1)and(ss[i,a,b]/i<ans)
       then ans:=ss[i,a,b]/i;
    if ans<>maxlongint then writeln(g,ans:0:3) else writeln(g,'OMG!');

  end;





 close(f);close(g);
end.