luogu#P2784. 化学1(chem1)- 化学合成
化学1(chem1)- 化学合成
题目背景
蒟蒻 HansBug 在化学考场上,挠了无数次的头,可脑子里还是一片空白。
题目描述
眼下出现在蒟蒻 HansBug 面前的是一个化学合成题,据他所知,一般答案如下面这样的格式:
(接下一行)
简单解释下:每种化合物可以通过一步反应生成另一个化合物(将这称作一步反应,设为 ),现在假设每个 中,理论上 个单位的 都仅可以生成 个单位的 。然而实际实验表明,并不存在绝对完全的化学转化,设转化率为 (即 个单位 实际可以生成 个单位的 ,)。
现在蒟蒻 HansBug 的知识体系中有 个这样 的转化。然而题目中蒟蒻 HansBug 要由 个单位的化合物 生成化合物 ,可是他脑细胞和 RP 已经消耗殆尽,所以找到最终产量最高的合成路线的艰巨任务就交给你啦!
输入格式
第一行为四个整数:,分别表示总共出现的化合物个数、HansBug 所知道的反应个数、起始的化合物序号、终末的化合物序号()。
第 行每行为两个整数和一个实数:,分别表示第 个反应为由 个单位的 化合物生成 单位的 化合物。
输出格式
一行,包含一个实数,为最佳路线下最终的产量(四舍五入保留 位小数),如果没有可行路线的话,输出 orz
。
3 3 1 3
1 3 0.8
1 2 0.9
2 3 0.9
0.8100
3 3 2 1
1 3 0.8
1 2 0.9
2 3 0.9
orz
提示
样例 1 和样例 2 中,两条合成路线分别为 、、,产率分别为 、、。
在样例 1 中,有两种可行的路线 和 ,最终产量分别为 、,故第二条路线更优,产量为 。
样例 2 中, 只能生成 , 无法生成别的化合物,故无法生成,蒟蒻 HansBug 只好选择 orz
。
【数据范围】