#P1730. 最小密度路径
最小密度路径
题目描述
给出一张有 个点 条边的加权有向无环图,接下来有 个询问,每个询问包括 个节点 和 ,要求算出从 到 的一条路径,使得密度最小(密度的定义为,路径上边的权值和除以边的数量)。
输入格式
第一行包括两个整数 和 。
以下 行,每行三个数字 ,表示从 到 有一条权值为 的有向边。
再下一行有一个整数 。
以下 行,每行一个询问 和 ,如题意所诉。
输出格式
对于每个询问输出一行,表示该询问的最小密度路径的密度(保留 位小数),如果不存在这么一条路径输出“OMG!”(不含引号)。
3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3
5.000
5.500
提示
,,,