P8906

很妙的一道题，结合了 meet in the middle 的思想。

思路

考虑将路径长度 $K$ 拆分为 $k_1 = \lfloor K/2 \rfloor$ 和 $k_2 = K - k_1$。

定义 $f[k][i]$ 为从起点 $1$ 到结点 $i$ 经过 $k$ 条边的最短路径权值。定义 $g[k][i]$ 为从结点 $i$ 到终点 $N$ 经过 $k$ 条边的最短路径权值。任何长度为 $K$ 的路径都可以看作是 $1 \to i$ 和 $i \to N$ 的拼接。

要移除边 $(u, v)$ 时，只需要检查那些恰好经过该边的路径。如果移除的边是当前最优路径的一部分，则该状态可能失效，需要重新扫描所有可能的转移来更新该状态。

时间复杂度是 $O(K \cdot N^3)$。