| 比赛 | 
    10101115 | 
    评测结果 | 
    WEWWEEEEEE | 
    | 题目名称 | 
    最小密度路径 | 
    最终得分 | 
    0 | 
    | 用户昵称 | 
    Des. | 
    运行时间 | 
    0.000 s  | 
    | 代码语言 | 
    Pascal | 
    内存使用 | 
    0.00 MiB  | 
    | 提交时间 | 
    2010-11-15 10:10:25 | 
显示代码纯文本
program path;
var b:array[1..50,1..50]of integer;
    f:array[1..50,1..50]of real;
    l:array[1..50,1..50]of integer;
    t,k,m,n,i,j: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
    f[t,k]:=maxint;
for t:=1 to m do
  begin
    readln(i,j,k);
    f[i,j]:=k;
    l[i,j]:=1;
  end;
for i:=1 to n do
  for t:=1 to n do
    for k:=1 to n do
      if (i<>t)and(i<>k)and(t<>k)and(f[t,i]<maxint)and(f[i,k]<maxint)
         and((f[t,i]*l[t,i]+f[i,k]*l[i,k])/(l[t,i]+l[i,k])<f[t,k]) then
           f[t,k]:=(f[t,i]*l[t,i]+f[i,k]*l[i,k])/(l[t,i]+l[i,k]);
readln(m);
for t:=1 to m do
  begin
   readln(i,j);
   if f[i,j]<maxint then
   writeln(f[i,j]:0:3)
   else writeln('OMG!');
  end;
close(output);
end.