「学习笔记」严格次短路

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

变量

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<pli, vector<pli>, greater<pli> > 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> 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<pli> e[N];
priority_queue<pli, vector<pli>, greater<pli> > 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;
}