化学1(chem1)- 化学合成

题目背景

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

题目描述

眼下出现在蒟蒻 HansBug 面前的是一个化学合成题,据他所知,一般答案如下面这样的格式: ![](https://cdn.luogu.com.cn/upload/pic/2223.png) (接下一行) ![](https://cdn.luogu.com.cn/upload/pic/2221.png) 简单解释下:每种化合物可以通过一步反应生成另一个化合物(将这称作一步反应,设为 $A\rightarrow B$),现在假设每个 $A\rightarrow B$ 中,理论上 $1$ 个单位的 $A$ 都仅可以生成 $1$ 个单位的 $B$。然而实际实验表明,并不存在绝对完全的化学转化,设转化率为 $C$(即 $1$ 个单位 $A$ 实际可以生成 $C$ 个单位的 $B$,$0<C<1$)。 现在蒟蒻 HansBug 的知识体系中有 $N$ 个这样 $A\rightarrow B$ 的转化。然而题目中蒟蒻 HansBug 要由 $1$ 个单位的化合物 $S$ 生成化合物 $T$,可是他脑细胞和 RP 已经消耗殆尽,所以找到最终产量最高的合成路线的艰巨任务就交给你啦!

输入输出格式

输入格式


第一行为四个整数:$N,M,S,T$,分别表示总共出现的化合物个数、HansBug 所知道的反应个数、起始的化合物序号、终末的化合物序号($1\le S,T\le N$)。 第 $2 \sim M+1$ 行每行为两个整数和一个实数:$A_i,B_i,C_i$,分别表示第 $i$ 个反应为由 $1$ 个单位的 $A_i$ 化合物生成 $C_i$ 单位的 $B_i$ 化合物。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

0.8100

输入样例 #2

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

输出样例 #2

orz

说明

样例 1 和样例 2 中,两条合成路线分别为 $1\rightarrow3$、$1\rightarrow2$、$2\rightarrow3$,产率分别为 $0.8$、$0.9$、$0.9$。 在样例 1 中,有两种可行的路线 $1\rightarrow3$ 和 $1\rightarrow2\rightarrow3$ ,最终产量分别为 $0.8$、$0.9\times0.9=0.81$,故第二条路线更优,产量为 $0.8100$。 样例 2 中,$2$ 只能生成 $3$,$3$ 无法生成别的化合物,故无法生成,蒟蒻 HansBug 只好选择 `orz`。 **【数据范围】** ![](https://cdn.luogu.com.cn/upload/pic/2220.png)