P4467 [SCOI2007]k短路

约瑟夫用脑玩 · 2021-12-28 16:27:18 · 题解

请求撤下所有“A Star”的题解，因为都不是正解而是乱搞，对思考没有任何意义，而且会误导其他人认为“A Star”可做或是直接觉得这就是正解。

讽刺的是现有题解都是“A Star”。

对以上叙述进行补充：“A Star”的复杂度是错的，而且一定是可以被卡掉的，如果是打表的不必说，如果是剪枝跑过的是数据水了。

这道题的正解也颇为简单，不要把07年的题想太复杂，做法就是真·k短路。

最短路大家都会吧，我们先考虑如何求出次短路。

经典的做法是把最短路上的每一条边都尝试删掉后跑最短路，再取其中的最小，原因显然，因为考虑了所有除了最短路的路径。

事实上这样并不利于我们进行扩展，因为每次考虑的路径中是有重复的。

考虑稍加限制但仍是正确的次短路做法：

• 我们钦定已经走了当前最短路的一个前缀。

• 限制下一条边不能走最短路走的那条边。

• 然后求出从这个前缀的最后一个点到终点的最短路。

• 同样的取其中的最小。

这个做法的正确性事实上是基于我们钦定除去最短路，然后求出来的最短路就是次短路了。

但我们还有一个重要的事实需要说明，就是我们只取了一部分最短路来取其中的最小，而其他路径都没有直接进行比较。

原因是这些路径一定可以通过截取某个前缀说明不可能是当前最短路的，请读者多作思考，后面扩展有用到这一点，故后文不会再做重复。

这个做法有一个最重要的好处是这些路径并不重复，更重要的，我们直接将这个方法扩展到k短路这道题就做完了，具体做法如下。

• 初始求出最短路。

  以下的思路是：每次去除当前的最短路，快速找到下一个最短路，直到求出k短路。

• 我们维护可能的下一个最短路的集合，删掉当前最短路后会新增一些路径可能成为下一个最短路。

  这些路径就是上述所说的方法求得，即钦定前缀，限制一条边，求最短路。

• 为了不和已有的可能的下一个最短路集合中的路径重复，当前钦定的前缀应不少于之前已有钦定的前缀。

正确性前面大概都说了，如果还有不清楚的，可能是我觉得不好说就略过了，还请读者多培养自行思考的能力，或是直接来找我问也行。

给一份复杂度正确且能通过这道题的代码。（长得不好看可以自行调整）

补充复杂度及细节：

• 时间复杂度 O(nk\times n^2)，前面的 nk 是总共涉及到的路径条数，n^2 是最短路时间。

• 空间复杂度是 O(nk\times (n/k/n^2))，前面的还是涉及到的路径条数，后面根据是否精细实现来看，我比较懒所以实现的是 O(k) 的，而且实际常数应该不大。

• 细节的话首先要注意字典序。

• 然后还要注意限制边可能限制多条。

• 最后建议用 O(n^2) 的最短路，因为 O(m\log m=n^2\log) 又难写又慢。

• 哦还有堆的 < 是反的大家应该都知道吧。

• 最后吐槽一下其实可以把k条最短路都输出出来的。。。