设 $\mathrm{dis}(u)$ 是从 $u$ 到 $n$ 的期望步数。考虑如何计算 $\mathrm{dis}(u)$：将 $u$ 的所有出边排序，使得 $\mathrm{dis}(v_1)\le \mathrm{dis}(v_2)\le \cdots\le \mathrm{dis}(v_d)$。则最优策略是对某个 $k$，依次尝试走向 $v_1,v_2,\ldots,v_k$，如果都不成功则不断尝试 $v_1$ 直到成功。这个转移是存在环的，但是容易证明不可能走向 $\mathrm{dis}$ 更大的点，因此用 Dijkstra 算法求解即可。时间复杂度 $O(m\log n)$。