代码随想录第六十六天打卡

今天大家会感受到 Bellman_ford 算法系列在不同场景下的应用。

建议依然是：一刷的时候，能理解 原理，知道Bellman_ford 解决不同场景的问题 ，照着代码随想录能抄下来代码就好，就算达标。

二刷的时候自己尝试独立去写，三刷的时候 才能有一定深度理解各个最短路算法。

Bellman_ford 队列优化算法（又名SPFA）

代码随想录

#include <iostream>
#include <list>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
struct Edge {
	int to;
	int val;
	Edge(int to,int val):to(to),val(val){}
};
void solve() {
	int n, m, v1, v2, val;
	cin >> n >> m;
	vector<list<Edge>>grid(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> val;
		grid[v1].push_back({ v2,val });
	}
	int start = 1;
	int end = n;
	vector<int>minDist(n + 1, INT_MAX);
	vector<bool>isInQueue(n + 1);
	queue<int>que;
	minDist[start] = 0;
	que.push(start);
	while (!que.empty()) {
		int node = que.front();
		que.pop();
		isInQueue[node] = false;
		for (Edge edge : grid[node]) {
			int to = edge.to;
			int from = node;
			int value = edge.val;
			if (minDist[to] > minDist[from] + value) {
				minDist[to] = minDist[from] + value;
				if (isInQueue[to]==false) {
					que.push(to);
					isInQueue[to] =true;
				}
			}
		}
	}
	if (minDist[end] == INT_MAX)cout << "unconnected" << endl;
	else cout << minDist[end] << endl;
}

int main() {
	solve();
	return 0;
}

bellman_ford之判断负权回路

代码随想录

#include <iostream>
#include <vector>
#include <list>
#include <climits>
#include <queue>
using namespace std;


void solve() {
	int n, m, v1, v2, val;
	cin >> n >> m;
	vector<vector<int>>grid;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> val;
		grid.push_back({v1, v2,val });
	}
	int start = 1;
	int end = n;
	bool flag = false;
	vector<int>minDist(n + 1,INT_MAX);
	minDist[start] = 0;
	for (int i = 1; i <= n; i++) {
		for (vector<int>& side : grid) {
			int from = side[0];
			int to = side[1];
			int price = side[2];
			if (i < n) {
				if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + side[2])minDist[to] = minDist[from] + side[2];
			}
			else {
				if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + side[2])flag = true;
			}
		}
	}
	if (flag)cout << "circle" << endl;
	else if (minDist[end] == INT_MAX) {
		cout << "unconnected" << endl;
	}
	else {
		cout << minDist[end] << endl;
	}
}
	
int main() {
	solve();
	return 0;
}

使用队列

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
	int to, val;
	Edge(int to,int val):to(to),val(val){}
};
void solve() {
	int n, m, v1, v2, val;
	cin >> n >> m;
	vector<list<Edge>>grid(n + 1);
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> val;
		grid[v1].push_back(Edge(v2, val));
	}
	int start = 1;
	int end = n;
	vector<int>minDist(n + 1,INT_MAX);
	minDist[start] = 0;
	queue<int>que;
	que.push(start);
	vector<int>count(n + 1, 0);
	count[start]++;
	bool flag = false;
	while (!que.empty()){
		int node = que.front();
		que.pop();
		for (Edge edge : grid[node]) {
			int from = node;
			int to = edge.to;
			int value = edge.val;
			if (minDist[to] > minDist[from] + value) {
				minDist[to] = minDist[from] + value;
				que.push(to);
				count[to]++;
				if (count[to] == n) {
					flag = true;
					while (!que.empty())que.pop();
					break;
				}
			}
		}
	}
	if (flag)cout << "circle" << endl;
		else if (minDist[end] == INT_MAX) {
			cout << "unconnected" << endl;
		}
		else {
			cout << minDist[end] <<endl;
		}
}
int main() {
	solve();
	return 0;
}

bellman_ford之单源有限最短路

代码随想录

#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <climits>
using namespace std;

void solve() {
	int start,end,k,n, m, v1, v2, val;
	cin >> n >> m;
	vector<vector<int>>grid;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> val;
		grid.push_back({ v1,v2,val });
	}
	cin >> start >> end >> k;
	vector<int>minDist(n + 1, INT_MAX);
	minDist[start] = 0;
	vector<int>minDist_copy(n + 1);
	for (int i = 1; i <= k + 1; i++) {
		minDist_copy = minDist;
		for (vector<int>& side : grid) {
			int from = side[0];
			int to = side[1];
			int price = side[2];
			if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) {
				minDist[to] = minDist_copy[from] + price;
			}
		}
	}
	if (minDist[end] == INT_MAX)cout << "unreachable" << endl;
	else cout << minDist[end] << endl;
}
int main() {
	solve();
	return 0;
}

总结

这个题看的有点不是太懂，二刷继续。