最短路与次短路

最短路算法不再赘述，假定我们已经求出了最短路，记 \(f[x, y]\) 为 \(x\) 到 \(y\) 的最短路。

记 \(g[x, y]\) 为 \(x\) 到 \(y\) 的严格次短路。

最短路树的定义

单源最短路问题中，如果p1->p2->p3->...pn是一条最短路，就将它的边都加入图中。

将所有的最短路径都这样处理，得到的图就是最短路树。

最短路和次短路的性质

假定图中不存在0环（有的话，0环不影响路径长度，对于只求长度的题无影响；有0环，路径有无数条，不可能求方案，对求方案数的题也无影响）。

• 任何一条最短路的路径中，一定不经过重复的点。

假设出现了，那就是一个环，因为没有0环和负环，去掉之后一定更小，与它是最短路径矛盾。

• 任何一条次短路中，重复的点出现的次数一定不超过2次

同样，如果出现了至少3次，那么就会出现多于2个正环。全部正环去掉之后，就是最短路径；只保留一个正环，此时路径长度（记为 \(cur\)）严格大于最短路径；而此路径上有两个正环，它一定大于 \(cur\)。

也就是存在一个路径 \(x\) ，使得最短路 \(d < x < y\)，那么 \(y\) 肯定就不是次短路了，因为次短路是除了最短路外最小的一条路径。

这些性质也许有用，也许没用

严格次短路的求法

我们将最短路树（就是那个DAG）建出来，设为 \(G\)。

那么，非最短路径一定有一条边不在 \(G\) 中。

假设所有边都在 \(G\) 中，而最短路树保证了走到每个点的路径长度都是起点到它的最短路，这就与此路径为非最短路径矛盾。

我们要求的就是所有非最短路径的长度构成的集合 \(S\) 中的最小值。

将 \(S\) 按照从起点出发，第一条不在 \(G\) 中的边 分类。

假设当前求的是从起点出发，第一条不在 \(G\) 中的边是 \((u, v)\) 的最小值。

需要注意，不论是无向图还有有向图，走的路径都是有顺序的，所以 \(G\) 中都是有向边。

条件限制了一定经过 \((u, v)\) 而从起点到 \(u\)，从 \(v\) 到终点的走法都是相对独立的，因此此子集的最小值就是 \(f[start, u] + w(u, v) + f(v, end)\)。

枚举每一条不在 \(G\) 中的边 \((u, v)\)，\(S\) 的最小值就是 \(f[start, u] + w(u, v) + f(v, end)\) 的最小值。

这样就求出了次短路。

非严格次短路的求法

先求出严格次短路。

将起点到终点的所有路径的长度的集合设为 \(S\)。

那么 \(S = \{f[start, end], f[start, end], ... , f[start, end], g[start, end], ...\}\)

也就是在 \(G\) 里判断一下终点的来边是否有超过1条。

如果只有1条来边，非严格次短路就是严格次短路；
如果有超过1条来边，非严格次短路就是最短路。

例题

P2865 [USACO06NOV] Roadblocks G 裸的严格次短路。

P2829 大逃离

题目描述有问题。

根据题意把走不到的点删掉，求严格次短路即可。

假如，我是说假如，题目中的最短路是可以走连接的点小于 \(k\) 的点，但是次短路不行，这样的严格次短路该怎么求呢？

假设原图的最短路树是 \(G\)，删去不可达点后的图的是 \(G'\)。

同样枚举每条不在 \(G\) 中的边，但是 \(f[start, u]\) 应当是 \(G'\) 中的最短路（分析见上）。

注意：此时判断一条边是否为 \(G\) 中的边，要用原图的 \(f\) 来判断，但是计算的式子，要用 \(G'\) 的 \(f\) 来求。