公交线路"/>
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
更多推荐
leetcode每日一题—815.公交线路
发布评论