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 <= 105
• routes[i] 中的所有值 互不相同
• sum(routes[i].length) <= 105
• 0 <= routes[i][j] < 106
• 0 <= source, target < 106

BFS 困难 每日一题

代码

1. 朴素 bfs，对车站建图

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        stations = defaultdict(set)
        for i, route in enumerate(routes):
            for station in route:
                    stations[station].add(i)
        if not stations[source] or not stations[target]:
            return -1
            
        routes = [set(x) for x in routes]

        queue = deque([(source,0)]) # cur_station, last_route, step
        visited_s = {source} # 记录到过的站点
        visited_r = [False] * (i+1) # 记录乘过的巴士
        while queue:
            cur_station, step = queue.popleft()
            for next_route in stations[cur_station]: # 遍历能乘坐的线路
                if visited_r[next_route]:
                    continue
                for next_station in routes[next_route] -visited_s:
                    if next_station == target:
                        return step + 1
                    queue.append((next_station, step+1))
                    visited_s.add(next_station)
                visited_r[next_route] = True
        return -1

2. 对路线建图

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source==target:
            return 0
        # s2r[station_id]=[route_0,route_1,...,route_k] ，记录站点有哪些公交线路
        s2r = defaultdict(list) # 带default的字典类，元素为list
        for route_id,route in enumerate(routes):    # 遍历每条线路
            for station_id in route:    # 记录每个站点有哪些线路经过
                s2r[station_id].append(route_id)
        graph=[set() for route_i in range(len(routes))] # 线路之间邻接图
        for adj_routes in filter(lambda l:len(l)>1,s2r.values()):   # 遍历每个站点经过的线路（筛选至少有两条线路的）
            for i,route_i in enumerate(adj_routes):     # 相邻线路之间构造邻接表
                graph[route_i]|=set(adj_routes[:i]+adj_routes[i+1:]) # python的set类， | 代表并集运算
        # BFS
        ans=0
        target_routes=set(s2r[target])  # 终点站所经过的线路集合
        queue=set(s2r[source])  # 队列初始化为起点站所经过的线路集合
        visit=set() #已经遍历过的线路集合（每一条线路至多只遍历一次）
        while queue:
            ans+=1 # 坐公交就要+1
            if len(queue&target_routes)>0:return ans    #与 target 在同一条线路上
            queue2=set()    # 后继节点集合，
            for route_i in queue:   # 先求所有与queue中线路相邻的线路
                queue2|=graph[route_i]  # | 是并集运算
            visit |= queue  # 记录已经visit的
            queue=queue2-visit  # 因为与queue中线路相邻的包含已经visit过的，故要做差集去掉。
        return -1   #无法到达target