卡码网KamaCoder 96. 城市间货物运输 III
题目来源:96. 城市间货物运输 III
C++题解1(来源代码随想录):bellman_ford
对所有边松弛一次,相当于计算 起点到达 与起点一条边相连的节点 的最短距离。本题是最多经过 k 个城市, 那么是 k + 1条边相连的节点。
但如果不依赖上一次松弛后minDist,在对所有边松弛第一次的过程中,不仅仅 与起点一条边相连的节点更新了,所有节点都更新了。而且对所有边的后面几次松弛,同样是更新了所有的节点,说明 至多经过k 个节点 这个限制 根本没有限制住,每个节点的数值都被更新了。因为计算minDist数组的时候,基于了本次松弛的 minDist数值,而不是上一次 松弛时候minDist的数值。
所以在每次计算 minDist 时候,要基于 对所有边上一次松弛的 minDist 数值才行,所以我们要记录上一次松弛的minDist。
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main() {
int src, dst,k ,p1, p2, val ,m , n;
cin >> n >> m;
vector<vector<int>> grid;
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid.push_back({p1, p2, val});
}
cin >> src >> dst >> k;
vector<int> minDist(n + 1 , INT_MAX);
minDist[src] = 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];
// 注意使用 minDist_copy 来计算 minDist
if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) {
minDist[to] = minDist_copy[from] + price;
}
}
}
if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
else cout << minDist[dst] << endl; // 到达终点最短路径
}
C++题解2(来源代码随想录):SPFA
使用SPFA算法解决本题的时候,关键在于 如何控制松弛k次。其实实现不难,但有点技巧,可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。下一轮松弛的时候,就把队列里 que_size 个节点都弹出来,就是上一轮松弛入队列的节点。
每一轮松弛中,重复节点可以不用入队列。因为重复节点入队列,下次从队列里取节点的时候,该节点要取很多次,而且都是重复计算。
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;
struct Edge { //邻接表
int to; // 链接的节点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1); // 邻接表
// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start, end, k;
cin >> start >> end >> k;
k++;
vector<int> minDist(n + 1 , INT_MAX);
vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果
minDist[start] = 0;
queue<int> que;
que.push(start); // 队列里放入起点
int que_size;
while (k-- && !que.empty()) {
vector<bool> visited(n + 1, false); // 每一轮松弛中,控制节点不用重复入队列
minDist_copy = minDist; // 获取上一次计算的结果
que_size = que.size(); // 记录上次入队列的节点个数
while (que_size--) { // 上一轮松弛入队列的节点,这次对应的边都要做松弛
int node = que.front(); que.pop();
for (Edge edge : grid[node]) {
int from = node;
int to = edge.to;
int price = edge.val;
if (minDist[to] > minDist_copy[from] + price) {
minDist[to] = minDist_copy[from] + price;
if(visited[to]) continue; // 不用重复放入队列,但需要重复松弛,所以放在这里位置
visited[to] = true;
que.push(to);
}
}
}
}
if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
else cout << minDist[end] << endl;
}
原文地址:https://blog.csdn.net/u010950122/article/details/142993172
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!