问题描述
有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
示例 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | from collections import deque
from typing import List
class Solution:
def findCheapestPrice(
self, n: int, flights: List[List[int]], src: int, dst: int, K: int
) -> int:
edges = [[-1] * n for _ in range(n)]
for u, v, w in flights:
edges[u][v] = w
q = deque([(src, 0, 0)])
ans = float("inf")
while q:
p, s, w = q.popleft()
if s > K + 1:
break
if p == dst:
ans = min(ans, w)
for j in range(n):
if edges[p][j] != -1 and w + edges[p][j] < ans:
q.append((j, s + 1, w + edges[p][j]))
return ans if ans != float("inf") else -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def findCheapestPrice(
self, n: int, flights: List[List[int]], src: int, dst: int, K: int
) -> int:
edges = [[-1] * n for _ in range(n)]
for u, v, w in flights:
edges[u][v] = w
ans = float("inf")
def dfs(p: int, s: int, w: int):
nonlocal ans
if s > K + 1:
return
if p == dst:
ans = min(ans, w)
for i in range(n):
if edges[p][i] != -1 and edges[p][i] + w < ans:
dfs(i, s + 1, edges[p][i] + w)
dfs(src, 0, 0)
return ans if ans != float("inf") else -1
|