[Python手撕]公交路线

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


        for i in range(len(routes)):
            for j in routes[i]:
                if j not in station_route:
                    station_route[j] = [i]
                else:
                    station_route[j].append(i)
        
        if source not in station_route:
            return -1


        queue = [(source,0)]
        visited_station = set()
        visited_station.add(source)
        visited_route = set()

        while queue:
            station,transfer = queue.pop(0)

            for next_route in station_route[station]:
                if next_route not in visited_route:
                    visited_route.add(next_route)
                    for next_station in routes[next_route]:
                        if next_station not in visited_station:
                            if next_station == target:
                                return transfer+1
                            visited_station.add(next_station)
                            queue.append((next_station,transfer+1))

        return -1