leetcode每日一题—815.公交线路

公交线路"/>

leetcode每日一题—815.公交线路

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

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

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

解答：

class Solution:def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:#stations:字典，记录每个车站可以乘坐的公交车stations=defaultdict(set)for i,stops in enumerate(routes):for stop in stops:stations[stop].add(i)#routes:列表，记录每辆公交车可以抵达的车站routes = [set(x) for x in routes]#q中的元组(cur,cost)用来记录：从source出发到当前车站cur所需要的花费q=deque([(source,0)])#buses:用来记录已经乘坐过的公交车buses=set()#stops:用来记录已经抵达过的车站stops={source}while q:cur,cost=q.popleft()if cur==target:return cost#遍历当前车站中还没有乘坐过的公交车：for bus in stations[cur]-buses:#该公交车线路可以抵达的车站for stop in routes[bus]-stops:buses.add(bus)stops.add(stop)q.append((stop,cost+1))return -1