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});//起点自己到自己的距离为0
        while(!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});//起点自己到自己的距离为0
        int 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];
    }
};