【最小密度路径】

题目描述

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

输入格式

第一行包括 2 个整数 N 和 M 。
以下 M 行,每行三个整数 A、B、W,表示从 A 到 B 有一条权值为 W 的有向边,每条边可能有重复的描述但权不一样。
再下一行有一个整数 Q 。
以下 Q 行,每行一个询问 X 和 Y,如题意所述。

输出格式

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

样例数据 1

输入

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

输出

5.000
5.500

备注

【数据范围】
对于60%的数据,有1 ≤ N ≤ 10,1 ≤ M ≤ 100,1 ≤ W ≤ 1000,1 ≤ Q ≤ 1000;
对于100%的数据,有1 ≤ N ≤ 50,1 ≤ M ≤ 1000,1 ≤ W ≤ 100000,1 ≤ Q ≤ 100000。

嘛……考试的时候并没有想到什么好的方法dfs搜索过了6个点。看到这道题第一反应是最短路径,想写个SPFA结果发现有除以边这个坑爹的条件破坏了权值判定,没想到是用Floyed做……不过要多加一层循环枚举(i,j)之间可能的边数v,至于输出,被那个double坑了半天,一定要×1.0不然会挂的很惨……

下面上代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*