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

解释:
城市航班图如下

示例 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]
航班没有重复，且不存在自环

方法1：
主要思路：解题汇总链接
（1）使用广度优先搜索；
（2）先将给定的航线转成有向图的邻接表进行存储，使用一个数组存储到各个地方的耗费，初始值置为最大INT_MAX；
（3）使用队列将出发点存储到队列中初始化，然后将每次中转中可以的到达的各个地方的耗费进行更新，获得当前中转下，各个地方的最小的耗费；
（4）注意在每次中转时，使用临时数组保存该次中转的结果，避免相互覆盖；
（5）直到最后中转次数用完，或队列为空；

class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {if(dst==src ){//起始点既终点，则直接返回0return 0;}vector<vector<pair<int,int>>> mp(n);//存储邻接表，元素同时存储了对应的耗费for(vector<int>& f:flights){mp[f[0]].push_back({f[1],f[2]});}vector<int> dist(n,INT_MAX);//初始值，到达各个点的耗费，初始值置为INT_MAXdist[src]=0;//起始点初始化queue<int> q;q.push(src);//队列初始化while(K-->=0&&!q.empty()){//终止条件int cur_size=q.size();//当前中转下，要是用的航站vector<int>tmp=dist;//辅助变量，存储该次中转下获得结果while(cur_size--){//当前中转下的各个航站遍历int cur_pos=q.front();//当前航站q.pop();for(pair<int,int>&p:mp[cur_pos]){//遍历各个可以到达的地方if(tmp[p.first]>dist[cur_pos]+p.second){//判断是否需要更新tmp[p.first]=dist[cur_pos]+p.second;q.push(p.first);//将更新过的航站重新放入队列，重新计算到达各个 位置的耗费}}}dist=tmp;//更新耗费}return dist[dst]==INT_MAX?-1:dist[dst];}
};