815. Bus Routes

https://leetcode.com/problems/bus-routes/

solution

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        graph = collections.defaultdict(list)
        visited = set()

        for i in range(len(routes)):
            for j in routes[i]:
                # {站点: 所属路线}
                graph[j].append(i)

        res = 0
        queue = collections.deque()
        queue.append(source)

        # BFS解法关键在于: 一次加入一个route的stop. 所以比常见最短路径多了一层for
        while queue:
            res += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for route in graph[node]:
                    if route in visited:
                        continue
                    visited.add(route)

                    for next_stop in routes[route]:
                        if next_stop == target:
                            return res
                        queue.append(next_stop)
        return -1

时间复杂度：O() 空间复杂度：O()