首先每个点直接走到点 \(n\) 的期望天数是知道的,所以可以将点 \(n\) 加入忽略集合,然后在剩下点中走来走去。
对于当前期望天数最少的那个点 \(i\),能走到点 \(n\) 就走,否则走自环。因为走到其它点最终也必须走到点 \(n\),而它们的期望天数都大于点 \(i\)。将点 \(i\) 接入忽略集合。
同样地,我们接着找出通过点 \(i\) 间接走到或不通过点 \(i\) 直接走到点 \(n\) 期望天数最小的点加入忽略集合。
重复上述过程,即每次找出通过忽略集合中的点到达点 \(n\) 期望天数最小的点加入忽略集合,更新贡献。类似 Dijkstra,正确性在于路径的确定性。
问题就是如何计算。考虑枚举每条可能的走的边:
\[E(u)=1+\left(\sum_i^{i\neq u}E(i)\times p_{u,i}\times\prod_{j}^{E_j<E_i}1-p_{u,j}\right)+E(u)\times\prod_i^{i\neq u}1-p_{u,i}
\]
\[E(u)\times\left(1-\prod_i^{i\neq u}1-p_{u,i}\right)=1+\left(\sum_i^{i\neq u}E(i)\times p_{u,i}\times\prod_{j}^{E_j<E_i}1-p_{u,j}\right)
\]
\[E(u)=\large\frac{1+\sum\limits_i^{i\neq u}E(i)\times p_{u,i}\times\prod\limits_{j}^{E_j<E_i}1-p_{u,j}}{1-\prod\limits_i^{i\neq u}1-p_{u,i}}
\]
分走自环的不走自环两种情况。