Java教程

「学习笔记」严格次短路

本文主要是介绍「学习笔记」严格次短路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

变量

n:点数;
m:边数;
evector 存图;
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;
}
这篇关于「学习笔记」严格次短路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!