思路讲解
这题的关键在于K站中转站内。
通过clone数组备份，确保每次松弛只松弛一次，不会连续松弛，确保不超出题设要求。
AC代码
https://leetcode.cn/problems/cheapest-flights-within-k-stops/submissions/615024531
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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……）