#P3470. Freda’s Walk
Freda’s Walk
Freda’s Walk
题目描述
雨后,Freda 和 Rainbow 想在 Poetic Island 散步。岛上的交通是一张有 个点、 条有向边的无环图。每条边都有给定的积水深度。
如果他们正位于 ,且目前从 出发的边的积水深度之和为 ,就以 的概率选取其中积水深度为 的一条边。到达没有出边的点时,散步结束。散步的路程是经过的边数。
出发前,他们可以决定在整个散步过程中忽略一条有向边,也可以保留所有边。忽略一条边后,选择概率只按仍然存在的边计算。求从 号点出发时,散步路程的最大期望。
输入格式
第一行包含两个正整数 ,分别表示点数和有向边数。
接下来 行,每行包含三个整数 ,表示一条由 指向 、积水深度为 的边。
输出格式
输出一行一个实数,表示最大期望,四舍五入保留六位小数。
样例 #1
4 5
0 1 2
0 2 1
0 3 3
1 3 1
2 3 4
2.000000
数据范围
,,,。