自动搬运

查看原文

来自洛谷，原作者为

	Feynman5210 **

搬运于2025-08-24 21:17:35，当前版本为作者最后更新于2025-05-22 17:53:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一年前很菜的自己没场切，现在来看看难度评级，发现评级和题解都是空的，于是写篇题解捡个漏。
类似多源最短路的形式，本质上是 dp。
首先求出每两点之间的最短距离 $dist_{i,j}$，用 Floyd 或 n 次 dfs 或 bfs 即可，时间复杂度 $O(n_{}^3)$。
然后求出每两点之间可能的路径条数 $path_{i,j}$，用 n 次 bfs 由前向后进行状态转移，转移方程
$path_{u,v}=\sum_{dist_{u,w}=dist_{u,v}-1}^{(v,w)}{path_{u,w}}$ 。复杂度 $O(n\times m)=O(n_{}^3)$
总复杂度 $O(n_{}^3)$，可过。大概评绿。