Description

给出一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

Input

第一行包括2个整数N和M。

以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。

再下一行有一个整数Q。

以下Q行，每行一个询问X和Y，如题意所诉。

Output

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

Sample Input

3 3

1 3 5

2 1 6

2 3 6

2

1 3

2 3

Sample Output

5.000

5.500

Hint

1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

题解

考虑转化成我们熟悉的问题解决。

由于都是求最小,很容易想到和此题类似的一个问题,求任两点间的最短路,能否借鉴 $Floyd$ 算法来解决呢?

本题不同点在于,还要除以一个边数。因为这个除法的缘故,使得 $Floyd$ 算法的最优子结构性质被破坏,假设存在路径 $i -> k -> j$,它的最小密度路径并不一定是 $i -> k$ 的最小密度路径加上 $k -> j$ 的最小密度路径。

例:设$[A, B]$表示路径的权值和为 $A$,通过了 $B$ 条边。假设从 $i -> k$ 存在着两条路径 $L1[2, 3]$以及 $L2[8, 10]$,从 $k -> j$ 存在着两条路径 $L3[1, 2]$以及 $L4[51, 100]$,很明显 $i -> k$ 的最小密度路径是 $L1$,$k -> j$ 的最小密度路径是 $L3$,但是 $i -> k -> j$ 的最小密度路径却是 $L1 + L4$。

有否办法去掉这个除法的影响?

回到问题特性,是有向无环图,一条路径最多只能经过 $N-1$条边,于是我们可以对边数进行枚举,即把答案的分母枚举了,剩下的就是让答案的分子最小化(答案是 权值和/边数),这就回到我们熟悉的问题:求最短。

在 $Floyd$ 的基础上重新划分阶段定义状态:

第 $k$ 个阶段表示恰好通过 $k$ 条边两点间的最短路,这样的话最优子结构以及无后效性都满足($k$ 的阶段的最优取值一定需要靠之前阶段的最优值,当然也不可能影响到之前阶段的取值了。)

定义状态 $f(i,j,k)$表示从 $i$ 到 $j$ 恰好经过 $k$ 条边的最短路,类似$Floyd$ 的算法得出 $DP$ 方程:

$$f(i,j,k)=Min(f(i,h,g)+f(h,j,k-g))$$

这个方程是 $5$ 维的,会超时,如何减小维数呢?

考虑在何处重复决策。注意到 $f(i,j,k)$的选择路径 $V1-V2-...-Vk$,实际上我们只要找到这里的一个点决策即可,而不需每个点都判断过去。这样就很容易想到在最后一个点进行决策。

$f(i,j,k)=Min(f(i,h,k-1)+f(h,j,1))$。数据范围不大,询问比较多,考虑用 $dp$ 直接算出所有点对的答案.因为密度 =$val \over R$ 所以考虑 $f[x][y][R]$ 为 $x=>y$ 经过 $R$ 条边的最小值 ,$ans={f[x][y][R] \over R}$

状态转移为:

$$f[i][j][R]=f[i][k][R-1]+f[k][j][1]$$

 

1 //It is made by Awson on 2017.10.30 2 #include 
     
       3 #include