(相关资料图)

出题人说：“有最短路，还要有次短路。”于是，就有了次短路这个东西。与次小生成树一样，目前不知道有啥用。本文求的是严格次短路！

变量

n：点数；m：边数；e：vector存图；dis1：储存最短路；dis2：储存次短路。

过程

我们要利用 dijkstra 的贪心思想和松弛操作。dijkstra 的贪心思想，就是用目前路径最短的点去更新其他点的最短路。松弛操作，即判断操作。

if (dis1[v] >= dis1[u] + w) {dis1[v] = dis1[u] + w;q.push({dis1[v], v});}

求严格次短路，我们先考虑次短路的值是怎么来的。

最短路被更新，原最短路的值转移到次短路上。新的路径大于最短路的长度，次短路还没有被更新。新的路径大于最短路的长度，且小于当前次短路的长度。\(u\) 节点的次短路更新后小于 \(v\) 节点当前的次短路。

知道怎么来的了，我们只需要最原来的 dijkstra 代码做出一点小小的修改即可。

priority_queue, greater > q;void dijkstra() {for (int i = 1; i <= n; ++ i) {dis1[i] = dis2[i] = 1e9 + 5;}dis1[1] = 0;q.push({0, 1});while (!q.empty()) {int u = q.top().second;q.pop();for (auto [w, v] : e[u]) {if (dis1[v] >= dis1[u] + w) {dis1[v] = dis1[u] + w;q.push({dis1[v], v});}else if (dis2[v] > dis1[u] + w) {dis2[v] = dis1[u] + w;q.push({dis1[v], v});}if (dis2[v] > dis2[u] + w) {dis2[v] = dis2[u] + w;}}}}

题目

[USACO06NOV]Roadblocks G模板题 可能次短路就是从这个题开始出现的

#include using namespace std;typedef long long ll;typedef pair pli;inline ll read() {ll x = 0;int fg = 0;char ch = getchar();while (ch < "0" || ch > "9") {fg |= (ch == "-");ch = getchar();}while (ch >= "0" && ch <= "9") {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}return fg ? ~x + 1 : x;}const int N = 5e3 + 5;int n, m;ll dis1[N], dis2[N];vector e[N];priority_queue, greater > q;void dijkstra() {for (int i = 1; i <= n; ++ i) {dis1[i] = dis2[i] = 1e9 + 5;}dis1[1] = 0;q.push({0, 1});while (!q.empty()) {int u = q.top().second;q.pop();for (auto [w, v] : e[u]) {if (dis1[v] >= dis1[u] + w) {dis1[v] = dis1[u] + w;q.push({dis1[v], v});}else if (dis2[v] > dis1[u] + w) {dis2[v] = dis1[u] + w;q.push({dis1[v], v});}if (dis2[v] > dis2[u] + w) {dis2[v] = dis2[u] + w;}}}}int main() {n = read(), m = read();for (int i = 1, x, y, z; i <= m; ++ i) {x = read(), y = read(), z = read();e[x].push_back({z, y});e[y].push_back({z, x});}dijkstra();printf("%lld\n", dis2[n]);return 0;}