LG#P1576. 最小花费
最小花费
题目描述
有 个人,编号为 。某些人的账户之间可以双向转账。若一对账户之间的手续费为 ,转出金额为 ,则接收金额为 。
可以经过若干人的账户进行连续转账,每次手续费都从当次转出的金额中扣除。请计算:要使编号为 的人最终收到 元,编号为 的人最少需要准备多少钱。
转账过程中按实数计算,不要在中间步骤把金额取整或四舍五入。保证 能向 转账,且最优答案不超过 。
输入格式
第一行输入两个整数 $n,m\left(1\leqq n\leqq2\times10^3;\ 1\leqq m\leqq10^5\right)$。
此后 行,每行输入三个整数 $u_i,v_i,z_i\left(1\leqq u_i,v_i\leqq n;\ 1\leqq z_i<100\right)$,表示两账户之间可以双向转账,扣除比例为 。
最后一行输入两个整数 ,代表转出人与最终接收人的编号。保证二者可达,且答案不超过 。
输出格式
输出最少需要的金额,保留小数点后 位。判题允许绝对误差不超过 。
测试样例
3 3
1 2 1
2 3 2
1 3 3
1 3
103.07153164
样例 1 解释
沿 转账,保留比例为 ,比直接转账保留的 更多。因此最少金额为 ,保留小数点后 位得到 。
2 1
1 2 99
1 2
10000.00000000