题目描述
有 n
个城市通过 m
个航班连接。每个航班都从城市 u
开始,以价格 w
抵达 v
。
现在给定所有的城市和航班,以及出发城市 src
和目的地 dst
,你的任务是找到从 src
到 dst
最多经过 k
站中转的最便宜的价格。如果没有这样的路线,则输出 -1
。
样例
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如上,从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200,如图中红色所示。
示例 2:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如上,从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500,如图中蓝色所示。
提示
n
范围是[1, 100]
,城市标签从0
到n - 1
。- 航班数量范围是
[0, n * (n - 1) / 2]
。 - 每个航班的格式
(src, dst, price)
。 - 每个航班的价格范围是
[1, 10000]
。 k
范围是[0, n - 1]
。- 航班没有重复,且不存在环路。
算法1
(堆优化 Dijkstra 求最短路) O(mlog(nK))
- 多个关键字的最短路径问题,
dis[i][j]
表示到达了第i
个点,且到达过j
个城市的最短距离。 - 剩下的都是堆优化 Dijkstra 的基本操作了,我们使用优先级队列代替普通队列。
时间复杂度
- 正常堆优化 Dijkstra 的时间复杂度,时间复杂度为 O(mlog(nk))。
- 但使用普通优先级队列实现,时间复杂度会达到 O(mlogm),因为队列中每个点不只出现一次。
空间复杂度
- 重建邻接表需要 O(m) 的空间,优先队列需要最多 O(m) 的空间。
C++ 代码
struct Node {
int no, stops;
int distance;
Node(int no_, int stops_, int distance_): no(no_), stops(stops_), distance(distance_) {}
bool operator > (const Node &other) const {
return distance > other.distance;
}
};
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
const int INF = 1000000000;
vector<vector<pair<int, int>>> graph(n);
for (const auto &v: flights)
graph[v[0]].emplace_back(v[1], v[2]);
K++;
vector<vector<int>> dis(n, vector<int>(K + 1, INF));
vector<vector<bool>> vis(n, vector<bool>(K + 1, false));
priority_queue<Node, vector<Node>, greater<Node>> q;
q.push(Node(src, 0, 0));
dis[src][0] = 0;
while (!q.empty()) {
Node u = q.top();
q.pop();
if (vis[u.no][u.stops])
continue;
vis[u.no][u.stops] = true;
for (const auto &v: graph[u.no])
if (u.stops + 1 <= K && dis[v.first][u.stops + 1] > dis[u.no][u.stops] + v.second) {
dis[v.first][u.stops + 1] = dis[u.no][u.stops] + v.second;
q.push(Node(v.first, u.stops + 1, dis[v.first][u.stops + 1]));
}
}
int ans = INF;
for (int i = 1; i <= K; i++)
ans = min(ans, dis[dst][i]);
if (ans == INF)
ans = -1;
return ans;
}
};
算法2
(Bellman-Ford) O(mK)
- 此题也可以看成典型的 Bellman-Ford 求最短路的问题,Bellman-Ford 定义了
dis[i][u]
表示经过了i
条边后,从源点到点u
的最短路径。 - 我们首先枚举
i
,然后用每条边更新一次dis[i]
数组。
时间复杂度
- 对于每一层,都需要 O(m) 的时间更新,故时间复杂度为 O(mK)。
空间复杂度
- 重建邻接表需要 O(m) 的空间。
C++ 代码
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
const int INF = 1000000000;
vector<vector<pair<int, int>>> graph(n);
for (const auto &v: flights)
graph[v[0]].emplace_back(v[1], v[2]);
K++;
vector<vector<int>> dis(K + 1, vector<int>(n, INF));
dis[0][src] = 0;
for (int i = 1; i <= K; i++)
for (int u = 0; u < n; u++)
for (const auto &v: graph[u])
dis[i][v.first] = min(dis[i][v.first], dis[i - 1][u] + v.second);
int ans = INF;
for (int i = 0; i <= K; i++)
ans = min(ans, dis[i][dst]);
if (ans == INF)
ans = -1;
return ans;
}
};
class Solution { public: //设f[i][cur]表示当前cur城市最多经过i站中转路线的最便宜的价格 //则f[i][cur] = min(f[i][cur],f[i-1][last] + cost) //last:表示上一站,cost表示从last到cur的花费。 //初始化:f[i][src] = 0 ,无论经过多少次,初始出发地的总花费均为0,其余为INF //最终结果:f[k+1][dst] int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { const int INF = 1e9; vector<vector<int>> f(k+2,vector<int>(n,INF)); f[0][src] = 0; for(int i = 1; i <= k + 1; ++ i){ f[i][src] = 0; for(const auto& x : flights) f[i][x[1]] = min(f[i][x[1]],f[i-1][x[0]] + x[2]); } return f[k+1][dst] >= INF ? -1 : f[k+1][dst]; } };
补个自己写的SPFA魔改版
typedef pair<int, int> PII; class Solution { public: const int N = 110; const int INF = 1e9; int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { //init vector<vector<PII>> adj(n+1, vector<PII> ()); for (auto e: flights) adj[e[0]].push_back({e[2], e[1]}); bool visited[n+10][K+10]; memset(visited, 0, sizeof visited); vector<vector<int>> dist(n+1, vector<int> (K+10, INF)); queue<PII> q; dist[src][0] = 0; q.push({src,0}); visited[src][0] = true; while (q.size()){ int u = q.front().first, k = q.front().second; q.pop(); visited[u][k] = false; for (auto e: adj[u]){ int len = e.first, v= e.second; if (dist[v][k+1] > dist[u][k] + len && k<=K){ dist[v][k+1] = dist[u][k] + len; if (!visited[v][k+1]){ q.push({v,k+1}); visited[v][k+1] = true; } } } } int res= INT_MAX; for (int i=0; i<=K+1; i++) res = min(res, dist[dst][i]); return res == INF? -1 : res; } };