#9335. 化学1(chem1)- 化学合成(洛谷 - P2784)
化学1(chem1)- 化学合成(洛谷 - P2784)
说明
眼下出现在蒟蒻 HansBug 面前的是一个化学合成题,据他所知,一般答案如下面这样的格式:
(接下一行)
简单解释下:每种化合物可以通过一步反应生成另一个化合物(将这称作一步反应,设为 A→B),现在假设每个 A→B 中,理论上 1 个单位的 A 都仅可以生成 1 个单位的 B。然而实际实验表明,并不存在绝对完全的化学转化,设转化率为 C(即 1 个单位 A 实际可以生成 C 个单位的 B,0<C<1)。
现在蒟蒻 HansBug 的知识体系中有 N 个这样 A→B 的转化。然而题目中蒟蒻 HansBug 要由 1 个单位的化合物 S 生成化合物 T,可是他脑细胞和 RP 已经消耗殆尽,所以找到最终产量最高的合成路线的艰巨任务就交给你啦!
输入格式
第一行为四个整数:N,M,S,T,分别表示总共出现的化合物个数、HansBug 所知道的反应个数、起始的化合物序号、终末的化合物序号(1≤S,T≤N)。
第 2∼M+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 中,两条合成路线分别为 1→3、1→2、2→3,产率分别为 0.8、0.9、0.9。
在样例 1 中,有两种可行的路线 1→3 和 1→2→3 ,最终产量分别为 0.8、0.9×0.9=0.81,故第二条路线更优,产量为 0.8100。
样例 2 中,2 只能生成 3,3 无法生成别的化合物,故无法生成,蒟蒻 HansBug 只好选择 orz
。
【数据范围】
原题链接