「学习笔记」严格次短路-Toy模板网

这篇具有很好参考价值的文章主要介绍了「学习笔记」严格次短路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

变量

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
模板题 ~~可能次短路就是从这个题开始出现的~~文章来源地址https://www.toymoban.com/news/detail-481085.html

#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;
}

到了这里，关于「学习笔记」严格次短路的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！