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

今天大家会感受到 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;
}