#6078. 「2017 山东一轮集训 Day7」重排

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

给定一个 n 个点 m 条边的边带权的 S-DAG,一个 S-DAG 即在一个有向无环图的基础上,可能会有若干的重边与自环。

你现在想从 s 点走到 t 点,当你每走到一个点 u 时, u 连出去的边的边权会等概率地随机排列,多次走到同一个点的话这个点的边权就会随机多次。一开始在 s 的时候也是会这样的。

你想尽快到达终点,因此想知道最小的期望距离是多少?

边权等概率地随机排列的意思是:设 u k 条出边,其指向的点为 v_1, v_2, \ldots, v_k ,边权为 c_1, c_2, \ldots, c_k ,那么边权会等概率地变成 c_1, c_2, \ldots, c_k 的全排列的一种。总共有 k! 种全排列。

当你走到点 u 时,其权值重新排列出的形状你是可以马上知道的,所以你可以根据新的权值来决策你的行动。

假如不可能到达则输出 -1

输入格式

第一行四个整数 n, m, s, t
接下来 m 行,每行三个数 u_i, v_i, c_i ,其中 u_i v_i 为整数, c_i 可能为浮点数。表示图中有一条从 u_i 出发到 v_i 的长度为 c_i 的边。

输出格式

输出一行一个浮点数,代表最小的期望距离,假如不可能到达输出 −1 。当你的答案与标准答案的绝对误差不超过 10 ^ {-6} 时会被视为正确。

样例

样例输入

4 4 1 3
1 2 1
2 3 6
2 4 3
1 1 3

样例输出

6.50000

数据范围与提示

对于 20\% 的数据, n, m \leq 100 ,每个点的出边数量不超过 5
对于 40\% 的数据, n, m \leq 200
另外有 20\% 的数据,给出的图中不存在自环;
对于 100\% 的数据, 1 \leq n, m \leq 1000; s \neq t; 0 \leq c_i \leq 100 c_i 的位数不超过 8 位。图中可能存在重边与自环。