都不知道什么时候做的题了
一开始很容易想到枚举断边然后 DP 算代价。
于是很容易想到 DP 状态定义：设 \(dp_u\) 为从 \(u\) 出发到 \(n\) 的期望步数。
那么显然有 \(dp_u = \sum^{v_n}_{v_1} \dfrac{dp_{v_{i}}}{d_u}\)，其中 \(d_u\) 为 \(u\) 的出度。
如果选择暴力枚举删边，总复杂度会到达 \(O(m \times (m + n))\)，需要优化。
我们观察式子可以发现，为了让期望最小，显然应该把最大的 \(dp_{v_i}\) 去掉。
所以只用枚举点，然后考虑断掉最大的那个就可以了。
时间复杂度为 \(O(n \times (n + m))\)
标签：ABC144F,solution,times,枚举,dp,DP From： https://www.cnblogs.com/Carousel/p/17737592.html