LeetCode 787. K 站中转内最便宜的航班
原题链接
中等
作者:
我是java同学
,
2023-11-27 22:18:44
,
所有人可见
,
阅读 46
const int N = 110, M = N * (N - 1) / 2;
struct Edge {
int a, b, w;
}edges[M];
int dist[N], backup[N];
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& f, int src, int dst, int k) {
k ++ ;
for (int i = 0; i < f.size(); i ++ ) {
int a = f[i][0], b = f[i][1], w = f[i][2];
edges[i] = {a, b, w};
}
memset(dist, 0x3f, sizeof dist);
dist[src] = 0;
for (int i = 0; i < k; i ++ ) {
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < f.size(); j ++ ){
auto e = edges[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
}
}
if (dist[dst] > 0x3f3f3f3f / 2) return -1;
return dist[dst];
}
};