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

program path;
var b:array[1..50,1..50,0..50]of integer;
    f:array[1..50,1..50,0..50]of real;
    l:array[1..50,1..50,0..50]of integer;
    an:array[1..50,1..50]of real;
    t,k,m,n,i,j,g:longint;
begin
assign(input,'path.in');
reset(input);
assign(output,'path.out');
rewrite(output);
readln(n,m);
for t:=1 to n do
  for k:=1 to n do
    for j:=0 to n do
      f[t,k,j]:=1 shl 60;
for t:=1 to m do
  begin
    readln(i,j,k);
    if k<f[i,j,1] then
    f[i,j,1]:=k;
  end;
for t:=1 to n do
  for k:=1 to n do
    an[t,k]:=1 shl 60;
for t:=1 to n do
  f[t,t,0]:=0;
for j:=1 to n do
  for i:=1 to n do
    for t:=1 to n do
      for k:=1 to n do
        begin
          if (f[t,i,1]<maxlongint)and(f[i,k,j-1]<maxlongint)
             and((f[t,i,1]+f[i,k,j-1])<f[t,k,j]) then
               f[t,k,j]:=(f[t,i,1]+f[i,k,j-1]);
          if (an[t,k]>f[t,k,j]/j )and(f[t,k,j]<>maxlongint) then
            an[t,k]:=f[t,k,j]/j;
        end;


readln(m);
for t:=1 to m do
  begin
   readln(i,j);
   if an[i,j]<maxlongint then
   writeln(an[i,j]:0:3)
   else writeln('OMG!');
  end;
close(output);
end.