luogu#P2784. 化学1(chem1)- 化学合成

    ID: 6818 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>图论洛谷原创队列邻接矩阵邻接表

化学1(chem1)- 化学合成

题目背景

蒟蒻 HansBug 在化学考场上,挠了无数次的头,可脑子里还是一片空白。

题目描述

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

(接下一行)

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

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

输入格式

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

2M+12 \sim M+1 行每行为两个整数和一个实数:Ai,Bi,CiA_i,B_i,C_i,分别表示第 ii 个反应为由 11 个单位的 AiA_i 化合物生成 CiC_i 单位的 BiB_i 化合物。

输出格式

一行,包含一个实数,为最佳路线下最终的产量(四舍五入保留 44 位小数),如果没有可行路线的话,输出 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 中,两条合成路线分别为 131\rightarrow3121\rightarrow2232\rightarrow3,产率分别为 0.80.80.90.90.90.9

在样例 1 中,有两种可行的路线 131\rightarrow31231\rightarrow2\rightarrow3 ,最终产量分别为 0.80.80.9×0.9=0.810.9\times0.9=0.81,故第二条路线更优,产量为 0.81000.8100

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

【数据范围】