次短路讲解

例题：
蒜头君陷入了坐标系上的一个迷阵，迷阵上有 n 个点，编号从 1 到 n。蒜头君在编号为 1 的位置，他想到编号为 n 的位置上。蒜头君当然想尽快到达目的地，但是他觉得最短的路径可能有风险，所以他会选择第二短的路径。现在蒜头君知道了 n 个点的坐标，以及哪些点之间是相连的，他想知道第二短的路径长度是多少。

注意，每条路径上不能重复经过同一个点。

1≤n≤200

这道题我们需要去求次短路的长度。我们令图 G=(V,E)。

首先我们肯定是要去求最短路长度的。那么在求得 1 号点到其他点的最短路的时候，我们肯定也能够同时得到一条从 1 号点到 n 号点的最短路径。

那么，我们在更新最短距离的时候需要进行额外的标记，内容是到某个点的最短路径，最后一条边是从哪里出发过去的，我们可以开一个 pre 数组进行记录：

for (int j = h[v]; j != -1; j = edge[j].next) { // 更新最短距离
if (d[to] > d[v] + edge[j].to) {
d[to] > d[v] + edge[j].to
pre[to] = v; // 代表当前到 g[v][j].v 的最短路的最后一条边是从 v 出发
}
}

然后我们可以去把从 1 到 n 上的最短路的所有结点都取出来：

void getPath(int x) {
if (x == 1) {
return;
}
/
做点什么
/
getPath(pre[x]);
/
你也可以在这里选择做点什么
/
}

getPath(n);

就能把1~n里的所有节点取出来。

然后我们可以得到一个很显然的结论，在图 G 上 1 号点到 n 号点的次短路肯定是 G 的某个子图上 1 号点到 n 号点的最短路。于是我们现在就转变成了考虑在哪些子图上 1 号点到 n 号点的最短路可能会变成图 G 上 1 号点到 n 号点的次短路。

而构造这些子图，我们很明显需要切断 GG 上 1 号点到 n 号点的最短路。而因为我们需要求的是次短路，所以删掉一条边就好。所以我们在图 G 上得到一条从 1 号点到 n 号点的最短路径之后，枚举这条路径上的每一条边断掉，这样就可以形成一些子图，再对这些子图去做 1 号点到 n 号点的最短路，然后取最小值，便可以得到答案了。

而删除一条边，并不是真的需要去执行这个操作，你只需要在进行最短路算法的时候进行特判，当遇到这条被“删除”的边的时候不去处理就行了。

for (int j = h[v]; j != -1; j = edge[j].next) { // 更新最短距离
int to = edge[j].to;
if (x == v && y == to) { // 假设 x 到 y 的有向边是此次删除掉了的边
continue;
}
if (d[to] > d[v] + edge[j].len) { //注意这里你不要再去更新 pre 标记了，因为 pre 标记记录的是图 G 的相关信息
d[g[v][j].v] = d[v] + edge[j].len;
}
}

当然你需要注意的是，如果你删除的是一条 无向边，那么相当于删除了两条有向边，判断的时候需要千万小心。