Leetcode 787. K 站中转内最便宜的航班 C++

Leetcode 787. K 站中转内最便宜的航班

题目

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

测试样例

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

• n 范围是 [1, 100]，城市标签从 0 到 n - 1.
• 航班数量范围是 [0, n * (n - 1) / 2].
• 每个航班的格式(src, dst, price).
• 每个航班的价格范围是 [1, 10000].
• k 范围是 [0, n - 1].
• 航班没有重复，且不存在环路

题解

Dijkstra算法
对Dijkstra算法进行改进，我们记录最短路径的同时，需要记录种转个数，我们需要保证到达一个点种转个数小于等于k。详细过程见代码

代码

class Rote{
public:int city;int money;		//当前花费int midCity;		//种转站个数Rote(int city,int money,int midCity){this->city = city;this->money = money;this->midCity = midCity;}bool operator < (const Rote r) const{return money > r.money;}
};
class Edge{
public:int city;int money;Edge(int city,int money){this->city = city;this->money = money;}
};
class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {if(src == dst)   return 0;priority_queue<Rote> q;unordered_map<int,vector<Edge>> graph;int size = flights.size();for(int i=0; i<size; i++){			//邻接表形式构造图graph[flights[i][0]].push_back(Edge(flights[i][1],flights[i][2]));}vector<bool> visit(n,0);vector<int> minMoney(n,INT_MAX);visit[src] = 0;minMoney[src] = 0;for(int i=0; i<graph[src].size(); i++){			//初始化优先队列minMoney[graph[src][i].city] = graph[src][i].money;q.push(Rote(graph[src][i].city,graph[src][i].money,0));		//显然此时是直达，因此中转站为0}while(!q.empty()){Rote now = q.top();//cout<<now.city<<" "<<now.money<<" "<<now.midCity<<endl;if(now.city == dst) return now.money;q.pop();//if(visit[now.city]) continue;visit[now.city] = 1;for(int i=0; i<graph[now.city].size(); i++){if(!visit[graph[now.city][i].city] && now.midCity+1<=K){		//只要是一条符合中转站数目要求的路径，且最短花费未求出，我们就进行探索q.push(Rote(graph[now.city][i].city,now.money+graph[now.city][i].money,now.midCity+1));if(now.money+graph[now.city][i].money < minMoney[graph[now.city][i].city])		//只有变便宜了才更新数组minMoney[graph[now.city][i].city] = now.money + graph[now.city][i].money;}}}return -1;}
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。