水了道*2700
比较套路的题，首先设 $f_i$ 表示 $i \to n$ 的最优策略期望天数。
观察发现设 $S$ 为 $u$ 的后继 $v$ 的集合，将它们按照 $f_v$ 从小到大排序，最优策略一定是找一个 $k$，如果前 $k$ 各中出现了边，那么走 $f$ 最小的那个，否则原地不动。
也就是
$$f_u = 1 + \sum_{i=1}^k \left (\prod_{j=1}^{i-1} (1-p_{u,v_j}) \right ) \times p_{u,v_i} \times f_{v_i} + \prod_{i=1}^k (1-p_{u,v_j}) f_u$$
$$f_u = \frac{1 + \sum_{i=1}^k \left (\prod_{j=1}^{i-1} (1-p_{u,v_j}) \right ) \times p_{u,v_i} \times f_{v_i}}{1-\prod_{i=1}^k (1-p_{u,v_j})}$$
如果图是拓扑图，这时我们已经解决这个问题了，但是图中可能存在环。
如果 $v$ 要对 $u$ 产生贡献，那么 $f_v < f_u$ 是必须的，我们每次只需要在剩下的点中找到 $f$ 最小的点，这个点的 $f$ 一定不会再更新了，然后用这个点更新其他点。
如何更新呢？
设 $h_u = \prod_{i=1}^k (1-p_{u,v_j}), g_u = 1 + \sum_{i=1}^k \left (\prod_{j=1}^{i-1} (1-p_{u,v_j}) \right ) \times p_{u,v_i} \times f_{v_i}, f_u = \frac{g_u}{1-h_u}$，暴力更新即可。
