题解：B4584 [合肥市小学组 2026 T4] 信号接力

溶金落梧桐 · 2026-11-09 17:15:27 · 题解

我们需要知道具体关闭的方案吗？如果沿着这个思路会怎么做？

我们会枚举每一个点判断是否将其关闭，然后看看是否从起点到终点还有路径可以到达，最坏是 O(2^{N}\times N) 的复杂度。其中 N 是地图中所有点的数目。

想一下如果是最优的关闭情况，剩余的路径会是什么？

一定会是最短路！最短路会让剩余的中继器开的最少。

因此该题我们只需要求出起点到终点的最短路，然后用开着的中继器数量减去它就做完了，用 bfs 求即可，时间复杂度是 O(N)。但注意到题目的网格是 2\times n 的，所以你直接向右走，走不了向下/向上移动，然后继续往右走就行，用不到 bfs 算法。