LeetCode815(2021.6.28)

LC815. 公交路线

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        stations = defaultdict(set)
        for i, stops in enumerate(routes):
            for stop in stops: stations[stop].add(i)
        routes = [set(x) for x in routes]

        q = deque([(source, 0)])
        buses = set()
        stops = {source}
        while q:
            pos, cost = q.popleft()
            if pos == target: return cost
            for bus in stations[pos] - buses:
                for stop in routes[bus] - stops:
                    buses.add(bus)
                    stops.add(stop)
                    q.append((stop, cost + 1))
        return -1

发表评论