787. K 站中转内最便宜的航班（Bellman-Ford） · znzryb

## 思路讲解

这题的关键在于K站中转站内。

通过clone数组备份，确保每次松弛只松弛一次，不会连续松弛，确保不超出题设要求。

## AC代码

[https://leetcode.cn/problems/cheapest-flights-within-k-stops/submissions/615024531](https://leetcode.cn/problems/cheapest-flights-within-k-stops/submissions/615024531)

```cpp
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        const int INF=static_cast<int>(1e9)+7;
        vector<int> dist(n+5,INF);
        dist[src]=0;
        for(int limit=0;limit<=k;++limit){
            vector<int> clone(dist.begin(),dist.end());
            for(int i=0;i<flights.size();++i){
                int u=flights[i][0],v=flights[i][1],price=flights[i][2];
                if(dist[v]>clone[u]+price){
                    dist[v]=clone[u]+price;
                }
            }
        }
        return (dist[dst]==INF?-1:dist[dst]);
    }
};
```

## 心路历程（WA，TLE，MLE……）