题解：P4467 [SCOI2007] k短路

· · 题解

前言

Astar 又回来（活过来）啦！

先别急着说，Astar 肯定会被卡掉的啊，不可能过的。

来，先读完你再说。

估计有 99.9% 的可能不会被卡掉，如果被卡掉的话请在评论区留言或私信。

本文有一些非常巧妙的变换可以转成普通模型的时间复杂度。

注意：本题的证明会涉及到 dijkstra 的算法本质，所以若还没有了解（只会打模板的），请先去了解。

普通的 Astar 做法

很多人就是没认真看题，然后随便看了看，发现：这不就是 K 短路吗？

不不不。这道题还多了一个限制：每一个点只能走一次，且输出路径要按照字典序输出。

于是有一些人便在这个代码上面改了改，就提交了上去。

学过 A 算法的你肯定知道 A 的估价函数是 f(i)=g(i)+h(i)，其中 g(i) 是从起点 s 到 i 的路径长度，而 h(i) 是从点 i 到终点 t 的预估路径长度。

也就是说，A* 算法的时间复杂度优劣就看预估函数的质量和消耗的时间了。

在没有前面的每一个点只能走一次这个条件的情况下，A* 的时间复杂度最坏为 \mathcal O(kn \log n)。

可是，如果加上这个条件，然后再套用以前的 A* 算法，你会发现，你的预估函数 h(i) 和真实的最短路径函数 true(i) 差了非常多。

这样的话，可以构造一组数据使得你的程序出现各种奇怪的错误。

先放这个方法的代码：错误方法的代码。

我们来看到提交记录：

发现存在一组数据能够将我们 Hack 掉。

考虑其他方法：我们可不可以用预处理出从 t \to i 的最短路，使得这条路径上没有任何一个点是重复的吗？

显然，Hack 方法与上面一致，让你尽可能的经过环或者是尽可能经过重复的边即可。

那我们该怎么办呢？设计不出来一个好的预估算法，我们就做不出来这道题了。

这个时候，我们就需要跳出平常的思维了。

不寻常的思维

发现如果时间复杂度是 \mathcal O(kn \log n)，运算量大概只有 3000000（乘上字符串比较的常数），有点太少了。

考虑能否可以不进行预处理，直接需要什么就计算什么即可。

这样子的话，我们就可以设计出一个函数，求出从终点开始，不经过哪些点且不重复经过点的最短路。

时间复杂度就是平常的，\mathcal O(n \log n)，当然还会更短（因为有很多点无法经过）。

然后，我们可以对于每一个点在扩展的时候都做一次这个函数求出我们需要的信息，时间复杂度为 \mathcal O(kn^2 \log n^2)，化简之后就是 \mathcal O(pkn^2 \log n)，p 是字符串比较的常数。

能通过吗？大概计算一下计算量最坏为 1.5 \times 10^8，且还跑不满，可以通过此题。

我们来试图证明一下这个算法的正确性（当然，我并不会严谨的证明）。

首先，我们求一般模型的 k 短路的最坏时间复杂度为 \mathcal O(kn \log n)。

发掘一下一般模型（普通 K 短路）用 A* 求解有哪一些性质：

首先，显然的，第 3 条肯定满足。

我们是在实际需求的情况下去求解最短路的，也就是说求出来的最短路肯定是可以和当前的路径接上去的（根据前面的定义得出）。

所以第 1 条满足，当然第 2 条是满足的（不是预处理的，是实时计算的）。

所以该算法的时间复杂度为 \mathcal O(kn^2 \log n)。

本题就做完了，我会在结尾放上代码。

证明部分

Part 1

首先，考虑一个点 z 的最短路如何更新。

假设有一条当前到 x 的最短路径 A 和一条到 x 的次短路径 B（不严格的）。

然后，假设 A 路径经过了的点与 B 路径经过的点不一样（一样的话就不用证明了）。

假设 x \ne z。

显然，分讨几种情况：

  1. 点 z 不在 A,B 任何一条路径当中。
  2. 点 z 在 A 路径中，不在 B 路径中。
  3. 点 z 不在 A 路径中，但在 B 路径中。
  4. 点 z 在 A,B 两条路径当中。

显然，对于第一种情况，显然成立。

第二种情况，显然，B 路径已经比 A 长了，肯定也成立。

第三种情况，根据 dijkstra 的算法流程，若存在一条更短的路径从 A 路径的终点 x 继续延伸到 z 的话，那么就不会先更新 z 这个点。

但是，因为 z 在 B 路径中且不是终点，而且延伸出了 B 路径的后半部分，所以可以判断出 z 的最短路已经确定，所以无法用 A 路径更新 z，但是 B 路径已经更新了 z。

我们在设计这个算法的时候，只是说点 x 只管最短路径是什么，不管其他的次短路。没有说在遍历 z 点的时候，B 路径不能到 z 点去更新啊！再说，z 点确定的时候都还没有 A 路径呢！

所以，也成立。

第四种情况，直接用 A 或 B 路径从起点 s 到 z 的最短路去更新即可。显然也成立。

所以，证毕，只需保留最短路径即可。

常数优化

上面的常数确实是有一点不堪了，我们来尝试优化一下常数。

但是，我们就需要多证一个东西。

证明：最短路不会走环路

题目已经说了，是正权图，不可能存在负环。

所以，你只要走了一遍环，那么你走的路程就会更长。

若我们从 x 走到了 x（绕了一个环），再从 x 走到了终点 t，不如直接 x \to t，这个地方的证明比较简单，若还无法理解，建议先学习最短路的算法核心部分。

但是注意：K 短路是有可能走环的。

他有可能会在先前路径上多走几个环，来使得该长度不等于最短路径长度但是又只多一点的这种效果。

这就是说为什么 K 短路需要判断是否走了重复的点的原因。

代码如下：正解代码。