0815：公交路线（1964 分）

Ian

2017-03-25 约 455 字预计阅读 1 分钟次阅读

力扣第 815 题

题目

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。

示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

提示：

1 <= routes.length <= 500.
1 <= routes[i].length <= 10⁵
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

相似问题：

2361：乘坐火车路线的最少费用

分析

典型的 bfs，只是两个点通过公交线路的中介连接
为了防止重复遍历，同时维护公交线路和公交站的哈希表即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        d = defaultdict(list)
        for i,A in enumerate(routes):
            for a in A:
                d[a].append(i)
        Q = deque([(0,source)])
        vis,vis2 = set(),{source}
        while Q:
            w,u = Q.popleft()
            if u==target:
                return w
            for i in d[u]:
                if i not in vis:
                    vis.add(i)
                    for v in routes[i]:
                        if v not in vis2:
                            vis2.add(v)
                            Q.append((w+1,v))
        return -1

115 ms

目录

0815：公交路线（1964 分）

题目

分析

解答