概念补充
- 非严格次小值：最小值和次小值可以一样长。
- 严格最小值：最小值和次小值不可以一样长。
- 非严格次短路：一张图中非严格次小的路径。
- 严格次短路：一张图中严格次小的路径。
单元次短路求解方法
方法一：魔改 Dijkstra
用两个距离数组，分别记录最短路和次短路。
当最短路可以更新时，那么次短路就继承之前的最短路的长度。
当次短路可以更新，且次短路更新后不会超过最短路长度，那么次短路更新。
补充：上述方法当且仅当适用于严格次短路，非严格次短路可以去掉最后的次短路更新后不会超过最短路长度的判断。
补充几个注意事项。
- 包括距离数组，标记数组，堆等在 Dijkstra 上的操作，要开到 \(2\) 维，一维记录节点编号，一维记录在最短路上还是次短路上。
- 在更新最短路或次短路时，一定要重新加入到堆中。
补充：如果不开两维，那第一次到 \(v\) 这个点是作为最短路进来的，第二次到 \(v\) 这个点是作为次短路进来的，这个时候标记数组只记录了第一次，第二次就拦住了。
实现就和 Dijkstra 几乎一模一样。
代码部分见例题。
方法二：替换边
补充：这里的图指非负权图，实在不行写个 SPFA 也不是不行。
我们先引入一个最小路径图的概念。
如果从一个起点出发，到终点的最短路的路径，就叫做最小路径图。
当然，最小路径图不止一条，是可能有很多条的，最小路径图的数量可以用最短路计数的方法求解，Come Here。
设 \(u\) 的最短路为 \(dis_u\)，邻接点为 \(v\)，\(u\) 和 \(v\) 的权值为 \(w(u,v)\)。
判断一条边是否是最小路径图上的边，可以用判断 \(dis_u + w(u,v)\) 是否等于 \(dis_v\)，严格的话反过来判一下。
最小路径图有一个性质，任何路径的长度都是一样的，不然就可以选更小的路径，如果不一样，你一定是写错了。
而且有向图的最小路径图是个 DAG，当然，负权图除外，因为可能有负环。
根据上面的性质，我们可以枚举一条不是最小路径图上的边。
然后，假设路径是从 \(1\) 到 \(n\)，顶点为 \(u\) 和 \(v\)，边权为 \(w(u,v)\)。
令 \(d(i,j)\) 表示 \(i\) 到 \(j\) 的最短路。
那么新的路径的权值为 \(d(1,u) + w(u,v) + d(v,n)\)，就是前缀加后缀加当前边权。
看起来时间会爆炸，但是我们可以从 \(1\) 跑一遍 Dijkstra，从 \(n\) 跑一遍 Dijkstra，这样复杂度就降下来了。
代码部分见例题。