LeetCode第 787 题：K 站中转内最便宜的航班(C++)

787. K 站中转内最便宜的航班 - 力扣（LeetCode）

典型的dijkstra算法，几乎是固定优先级队列加上bfs（bfs求出的都是最大/最小）的思路了，这题多加了一个中转站的限制

不过我还是太年轻，代码并没有通过全部案例，第43个卡住了，主要问题是使用优先级队列的话，跳出循环的条件很难处理，k值和终点哪个作为判断依据暂时不明确。

class Solution {
public:struct cmp{//按照距离排序bool operator()(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b){return a.first.second < b.first.second;}};int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {vector<int> distance(n, INT_MAX);//记录该节点到起点的距离unordered_map<int, vector<pair<int, int>>> adj;//pair里面的两个元素分别表示顶点编号和距离for(const auto &v : flights)    adj[v[0]].push_back({v[1], v[2]});//构建邻接表//pair<pair<编号，到起点的距离>, 当前层次编号>，当前层次编号是用来记录中转站的priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, cmp> q;q.push({{src, 0}, 0});//起点自己到自己的距离为0while(!q.empty()){int cur = q.top().first.first, dis = q.top().first.second;int level = q.top().second;q.pop();if(level > K){break;}//考虑与当前节点cur相连（指向）的节点，并更新起点到他们的距离for(const auto &v : adj[cur]){if(distance[v.first] > dis + v.second){//更新距离distance[v.first] = dis + v.second;q.push({{v.first, distance[v.first]}, 1+level});}}}return distance[dst] == INT_MAX ? -1 : distance[dst];}
};

队列 + bfs

而且上述代码很臃肿，主要是因为使用pair嵌套来传递当前的层次（类似二叉树的层次遍历的思路）。但是层次遍历的时候其实是没有必要专门传递层数的，可以每次在while里面再使用一个for循环处理队列中的全部元素，这样一个while循环就是一层，具体还是看代码：

class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {//题目描述说不存在环，所以不用记录顶点是否访问过int res = INT_MAX;unordered_map<int, vector<pair<int, int>>> adj;//pair里面的两个元素分别表示顶点编号和距离for(const auto &v : flights)    adj[v[0]].push_back({v[1], v[2]});//构建邻接表//pair<编号，到起点的距离>queue<pair<int, int>> q;//使用普通队列而不是优先级队列q.push({src, 0});//起点自己到自己的距离为0int step = 0;while(!q.empty() && step <= K){int n = q.size();//事先记录size，一次while循环遍历一个层次for(int i = 0; i < n; ++i){int cur = q.front().first, dis = q.front().second;q.pop();//考虑与当前节点cur相连（指向）的节点，并更新起点到他们的距离for(const auto &v : adj[cur]){if(dis + v.second >= res)   continue;if(v.first == dst)  res = dis+v.second;else q.push({v.first, dis+v.second});}}++step;}return res == INT_MAX ? -1 : res;}
};

所以我还是常常把题目想得太复杂了，拿到题目就像往dijkstra算法上面去套。。。

Bellman-Ford

这个算法目前还不懂，但是看起来真的好厉害。

可以去看这儿的图;最短路径（三）—Bellman-Ford算法（解决负权边）_小地盘的诺克萨斯-CSDN博客

class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {vector<int> dp(n, INT_MAX/2);//src到各个位置的最短距离vector<int> backup(n);dp[src] = 0;for(int k = 0; k <= K; ++k){//k次松弛backup.assign(dp.begin(), dp.end());for(const auto &f : flights){//枚举所有的边if(dp[f[1]] > backup[f[0]] + f[2])  dp[f[1]] = backup[f[0]] + f[2];}}return dp[dst] == INT_MAX/2 ? -1 : dp[dst];}
};

可以稍作优化：

class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {vector<int> dis(n, INT_MAX/2);//src到各个位置的最短距离vector<int> backup(n);dis[src] = 0;for(int k = 0; k <= K; ++k){//k次松弛backup.assign(dis.begin(), dis.end());for(const auto &f : flights){//枚举所有的边if(dis[f[1]] > backup[f[0]] + f[2])  dis[f[1]] = backup[f[0]] + f[2];}if(backup == dis) break;//这一轮的松弛中每个顶点到起点的距离都没有变化}return dis[dst] == INT_MAX/2 ? -1 : dis[dst];}
};