* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)

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

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

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


![](https://file1.kamacoder.com/i/algo/20240319103900.png)

![](https://file1.kamacoder.com/i/algo/20240319103919.png)

![](https://file1.kamacoder.com/i/algo/20240319104026.png)


## 思路 



```CPP 
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> minDist(n , INT_MAX/2);
        minDist[src] = 0;
        vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
        for (int i = 1; i <= k + 1; i++) {
            minDist_copy = minDist; // 获取上一次计算的结果
            for (auto &f : flights) {
                int from = f[0];
                int to = f[1];
                int price = f[2];
                minDist[to] = min(minDist_copy[from] + price, minDist[to]);
                // if (minDist[to] > minDist_copy[from] + price) minDist[to] = minDist_copy[from] + price;
            }

        }
        int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
        return result;
    }
};
```

下面是典型的错误写法 

```CPP
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> minDist(n , INT_MAX/2);
        minDist[src] = 0;
        for (int i = 1; i <= k + 1; i++) {
            for (auto &f : flights) {
                int from = f[0];
                int to = f[1];
                int price = f[2];
                if (minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
            }
        }
        int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
        return result;
    }
};
```


-----------

SPFA 


class Solution {
struct Edge {
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> minDist(n , INT_MAX/2);
        vector<list<Edge>> grid(n + 1); // 邻接表
        for (auto &f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            grid[from].push_back(Edge(to, price));

        }
        minDist[src] = 0;
        vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
        k++;
        queue<int> que;
        que.push(src);
        std::vector<bool> visited(n + 1, false); // 可加，可不加，加了效率高一些，防止重复访问
        int que_size;
        while (k-- && !que.empty()) {

            minDist_copy = minDist; // 获取上一次计算的结果
            que_size = que.size();
            while (que_size--) { // 这个while循环的设计实在是妙啊
                int node = que.front(); que.pop();
                for (Edge edge : grid[node]) {
                    int from = node;
                    int to = edge.to;
                    int price = edge.val;
                    if (minDist[to] > minDist_copy[from] + price) {
                        minDist[to] = minDist_copy[from] + price;
                        que.push(to);
                    }
                }

            }
        }
        int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
        return result;
    }
};



队列加上 visited 不能重复访问

class Solution {
struct Edge {
    int to;  // 链接的节点
    int val; // 边的权重

    Edge(int t, int w): to(t), val(w) {}  // 构造函数
};

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> minDist(n , INT_MAX/2);
        vector<list<Edge>> grid(n + 1); // 邻接表
        for (auto &f : flights) {
            int from = f[0];
            int to = f[1];
            int price = f[2];
            grid[from].push_back(Edge(to, price));

        }
        minDist[src] = 0;
        vector<int> minDist_copy(n); // 用来记录每一次遍历的结果
        k++;
        queue<int> que;
        que.push(src);
        int que_size;
        while (k-- && !que.empty()) {
            // 注意这个数组放的位置
            vector<bool> visited(n + 1, false); // 可加，可不加，加了效率高一些，防止队列里重复访问，其数值已经算过了
            minDist_copy = minDist; // 获取上一次计算的结果
            que_size = que.size();
            while (que_size--) {
                int node = que.front(); que.pop();
                for (Edge edge : grid[node]) {
                    int from = node;
                    int to = edge.to;
                    int price = edge.val;
                    if (minDist[to] > minDist_copy[from] + price) {
                        minDist[to] = minDist_copy[from] + price;
                        if(visited[to]) continue; // 不用重复放入队列，但需要重复计算，所以放在这里位置
                        visited[to] = true;
                        que.push(to);
                    }
                }

            }
        }
        int result = minDist[dst] == INT_MAX/2 ? -1 : minDist[dst];
        return result;
    }
}; 



