A2133. 化学1（chem1）- 化学合成
编程题
普及/提高-
知识点
题目描述
每种化合物可以通过一步反应生成另一个化合物（将这称作一步反应，设为 $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 已经消耗殆尽，所以找到最终产量最高的合成路线的艰巨任务就交给你啦！
现在蒟蒻 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$ 化合物。
第 $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 只好选择
**【数据范围】**
N<=30,M<=30 。
在样例 1 中，有两种可行的路线 $1\rightarrow3$ 和 $1\rightarrow2\rightarrow3$ ，最终产量分别为 $0.8$、$0.9\times0.9=0.81$，故第二条路线更优，产量为 $0.8100$。
样例 2 中，$2$ 只能生成 $3$，$3$ 无法生成别的化合物，故无法生成，蒟蒻 HansBug 只好选择
orz。**【数据范围】**
N<=30,M<=30 。