题解：B4176 [BCSP-X 2024 6 月初中组] 道路选择

· · 题解

一年前很菜的自己没场切，现在来看看难度评级，发现评级和题解都是空的，于是写篇题解捡个漏。
类似多源最短路的形式，本质上是 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)，可过。大概评绿。