#9335. 化学1(chem1)- 化学合成(洛谷 - P2784)

化学1(chem1)- 化学合成(洛谷 - P2784)

说明

眼下出现在蒟蒻 HansBug 面前的是一个化学合成题,据他所知,一般答案如下面这样的格式:

(接下一行)

简单解释下:每种化合物可以通过一步反应生成另一个化合物(将这称作一步反应,设为 AB),现在假设每个 AB 中,理论上 1 个单位的 A 都仅可以生成 1 个单位的 B。然而实际实验表明,并不存在绝对完全的化学转化,设转化率为 C(即 1 个单位 A 实际可以生成 C 个单位的 B0<C<1)。

现在蒟蒻 HansBug 的知识体系中有 N 个这样 AB 的转化。然而题目中蒟蒻 HansBug 要由 1 个单位的化合物 S 生成化合物 T,可是他脑细胞和 RP 已经消耗殆尽,所以找到最终产量最高的合成路线的艰巨任务就交给你啦!

输入格式

第一行为四个整数:N,M,S,T,分别表示总共出现的化合物个数、HansBug 所知道的反应个数、起始的化合物序号、终末的化合物序号(1S,TN)。

2M+1 行每行为两个整数和一个实数:Ai,Bi,Ci,分别表示第 i 个反应为由 1 个单位的 Ai 化合物生成 Ci 单位的 Bi 化合物。

输出格式

一行,包含一个实数,为最佳路线下最终的产量(四舍五入保留 4 位小数),如果没有可行路线的话,输出 orz

3 3 1 3
1 3 0.8
1 2 0.9
2 3 0.9
0.8100

提示

样例 1 和样例 2 中,两条合成路线分别为 131223,产率分别为 0.80.90.9

在样例 1 中,有两种可行的路线 13123 ,最终产量分别为 0.80.9×0.9=0.81,故第二条路线更优,产量为 0.8100

样例 2 中,2 只能生成 33 无法生成别的化合物,故无法生成,蒟蒻 HansBug 只好选择 orz

【数据范围】


原题链接

Source

图论 队列 洛谷原创