参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！
787. K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
思路
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<int> minDist(n , INT_MAX/2);
minDist[src] = 0;
vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
for (int i = 1; i <= k + 1; i++) {
minDist_copy = minDist; // 获取上一次计算的结果
for (auto &f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
minDist[to] = min(minDist_copy[from] + price, minDist[to]);
// if (minDist[to] > minDist_copy[from] + price) minDist[to] = minDist_copy[from] + price;
}
}
int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
return result;
}
};下面是典型的错误写法
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<int> minDist(n , INT_MAX/2);
minDist[src] = 0;
for (int i = 1; i <= k + 1; i++) {
for (auto &f : flights) {
int from = f[0];
int to = f[1];
int price = f[2];
if (minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
}
}
int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
return result;
}
};SPFA
class Solution { struct Edge { int to; // 链接的节点 int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
public:
int findCheapestPrice(int n, vector<vector
}
minDist[src] = 0;
vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
k++;
queue<int> que;
que.push(src);
std::vector<bool> visited(n + 1, false); // 可加，可不加，加了效率高一些，防止重复访问
int que_size;
while (k-- && !que.empty()) {
minDist_copy = minDist; // 获取上一次计算的结果
que_size = que.size();
while (que_size--) { // 这个while循环的设计实在是妙啊
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;
que.push(to);
}
}
}
}
int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
return result;
}
};
队列加上 visited 不能重复访问
class Solution { struct Edge { int to; // 链接的节点 int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
public:
int findCheapestPrice(int n, vector<vector
}
minDist[src] = 0;
vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
k++;
queue<int> que;
que.push(src);
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);
}
}
}
}
int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
return result;
}
};
