LG#P1576. 最小花费

最小花费

题目描述

\hspace{15pt}有 nn 个人,编号为 1∼n1\sim n。某些人的账户之间可以双向转账。若一对账户之间的手续费为 z%z\%,转出金额为 pp,则接收金额为 p×(1−z/100)p\times(1-z/100)。

\hspace{15pt}可以经过若干人的账户进行连续转账,每次手续费都从当次转出的金额中扣除。请计算:要使编号为 bb 的人最终收到 100100 元,编号为 aa 的人最少需要准备多少钱。

\hspace{15pt}转账过程中按实数计算,不要在中间步骤把金额取整或四舍五入。保证 aa 能向 bb 转账,且最优答案不超过 10410^4。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(1\leqq n\leqq2\times10^3;\ 1\leqq m\leqq10^5\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,z_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq z_i<100\right)$,表示两账户之间可以双向转账,扣除比例为 zi%z_i\%。

\hspace{15pt}最后一行输入两个整数 a,b(1≦a,b≦n)a,b\left(1\leqq a,b\leqq n\right),代表转出人与最终接收人的编号。保证二者可达,且答案不超过 10410^4。

输出格式

\hspace{15pt}输出最少需要的金额,保留小数点后 88 位。判题允许绝对误差不超过 10−710^{-7}。

测试样例

3 3                                     
1 2 1
2 3 2
1 3 3
1 3
103.07153164

样例 1 解释

\hspace{15pt}沿 1→2→31\to2\to3 转账,保留比例为 0.99×0.98=0.97020.99\times0.98=0.9702,比直接转账保留的 0.970.97 更多。因此最少金额为 100/0.9702100/0.9702,保留小数点后 88 位得到 103.07153164103.07153164。

2 1
1 2 99
1 2
10000.00000000