用 C++ 查找 K 个经停点内最便宜的航班
假设我们有 n 个城市，由 m 个航班连接。每个航班从 u 出发，以 w 的价格抵达 v。如果我们有所有城市和航班，以及出发城市 src 和目的地 dst，那么我们的任务就是找到从 src 到 dst 最多经停 k 个经停点的最便宜价格。如果没有这样的路线，则返回 -1。
因此，如果输入为 n = 3、edges = [[0,1,100],[1,2,100],[0,2,500]]、src = 0、dst = 2、k = 1，则输出将为 200
为了解决这个问题，我们将遵循以下步骤 −
创建一个名为 Data 的数据结构，它可以保存节点、dist 和 val
定义一个 2D 数组成本
成本 := 一个阶数为 (n + 1) x (K + 10) 的二维数组，用无穷大填充
定义一个三维数组图
用于初始化 i := 0，当 i <航班数量，更新(将 i 增加 1)，执行 −
u := flights[i, 0]
v := flights[i, 1]
在 graph[u] 末尾插入 { v, flights[i, 2] }
定义一个优先级队列 q
将数据(src, 0, 0)插入 q
cost[src, 0] := 0
ans := -1
当(不是 q 为空)时，执行 −
temp := top element of q
curr := temp.node
从 q 中删除元素
dist := temp.dist
如果 curr 与 dst 相同，则 −
返回 temp.cost
(increase dist by 1)
如果 dist > K + 1，则 −
忽略以下部分，跳至下一次迭代
对于初始化 i := 0，当 i < size of graph[curr]，更新(将 i 增加 1)，执行 −
neighbour := graph[curr, i, 0]
如果 cost[neighbour, dist] > cost[curr, dist - 1] + graph[curr, i, 1]，然后 −
cost[neighbour, dist] := cost[curr, dist - 1] + graph[curr, i, 1]
将 Data(neighbour, dist, cost[neighbour, dist]) 插入 q
return -1
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
struct Data{
int node, dist, cost;
Data(int a, int b, int c){
node = a;
dist = b;
cost = c;
}
};
struct Comparator{
bool operator() (Data a, Data b) {
return !(a.cost < b.cost);
}
};
class Solution {
public:
vector<vector<int>> cost;
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
cost = vector<vector<int> >(n + 1, vector<int>(K + 10, INT_MAX));
vector<vector<int> > graph[n];
for (int i = 0; i < flights.size(); i++) {
int u = flights[i][0];
int v = flights[i][1];
graph[u].push_back({ v, flights[i][2] });
}
priority_queue<Data, vector<Data>, Comparator> q;
q.push(Data(src, 0, 0));
cost[src][0] = 0;
int ans = -1;
while (!q.empty()) {
Data temp = q.top();
int curr = temp.node;
q.pop();
int dist = temp.dist;
if (curr == dst)
return temp.cost;
dist++;
if (dist > K + 1)
continue;
for (int i = 0; i < graph[curr].size(); i++) {
int neighbour = graph[curr][i][0];
if (cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]) {
cost[neighbour][dist] = cost[curr][dist - 1] + graph[curr][i][1];
q.push(Data(neighbour, dist, cost[neighbour][dist]));
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,100},{1,2,100},{0,2,500}};
cout << (ob.findCheapestPrice(3, v, 0, 2, 1));
}
输入
3, {{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1
输出
200
