#P1730. 最小密度路径

最小密度路径

题目描述

给出一张有 NN 个点 MM 条边的加权有向无环图,接下来有 QQ 个询问,每个询问包括 22 个节点 XXYY,要求算出从 XXYY 的一条路径,使得密度最小(密度的定义为,路径上边的权值和除以边的数量)。

输入格式

第一行包括两个整数 NNMM

以下 MM 行,每行三个数字 A,B,WA,B,W,表示从 AABB 有一条权值为 WW 的有向边。

再下一行有一个整数 QQ

以下 QQ 行,每行一个询问 XXYY,如题意所诉。

输出格式

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

3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3
5.000
5.500

提示

1N501 \le N \le 501M10001 \le M \le 10001W1051\le W \le 10^51Q1051 \le Q \le 10^5