问题 25578. -- 最小密度路径

25578: 最小密度路径

时间限制: 1 Sec  内存限制: 128 MB
献花: 60  解决: 28
[献花][花圈]

题目描述

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

输入

第一行包括2个整数NM

2到第M+1行,每行三个数字ABW,表示从AB有一条权值为W的有向边。

M+2行只有一个整数Q

接下来Q行,每行有两个整数XY,表示一个询问。


对于40%的数据,有1N101M1001W10001Q1000

对于100%的数据,有1N501M10001W1000001 Q100000

输出

对于每个询问输出一行,表示该询问的最小密度路径的密度(保留3位小数),如果不存在从XY的一条路径,则输出“OMG!”。

样例输入

3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3

样例输出

5.000
5.500

提示

来源

[献花][花圈]