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

program   zuixiaomidulujing;
var
  n,m,i,j,k,p,q,a,b,w,x,y:longint;
  min:real;
  map:array[1..50,1..50,1..1000]of longint;
begin
  assign (input,'path.in');
  reset (input);
  assign (output,'path.out');
  rewrite (output);
    readln (n,m);
    for i:=1 to n do
      for j:=1 to n do
        for k:=1 to n do
          map[i,j,k]:=maxlongint;
    for i:=1 to m do
    begin
      readln (a,b,w);
      if w<=map[a,b,1] then
      map[a,b,1]:=w
    end;
    for k:=2 to n do
      for p:=1 to n do
        for i:=1 to n do
          for j:=1 to n do
            if (map[i,p,k-1]<>maxlongint)and(map[p,j,1]<>maxlongint) then
              if map[i,p,k-1]+map[p,j,1]<map[i,j,k] then
                map[i,j,k]:=map[i,p,k-1]+map[p,j,1];
    readln (q);
    for i:=1 to q do
    begin
      readln (x,y);
      min:=maxlongint;
      for j:=1 to n do
        if (map[x,y,j]<>maxlongint)and(map[x,y,j]/j<min) then
          min:=map[x,y,j]/j;
      if min<>maxlongint then
        writeln (min:0:3)
      else
        writeln ('OMG!')
    end;
  close (input);
  close (output)
end.