文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
**解析：**Version 1，从起始站出发，每一次乘车，按照广度优先进行搜索所有可能到达的车站，将所有可能的车站作为候选的下一次乘车的出发站，重新进行搜索，每一次搜索过的公交车路线要从总路线中剔除，直至没有候选的乘车站为止，由于搜索了很多不能换乘的无用车站，因此超时。Version 2，在Version 1的基础上进行改进，首先遍历所有路线，只保留可以换乘的车站、起始站和终点站，然后再执行Version 1的广度优先搜索，搜索时间大幅缩短，可以超过99%的方法。
- Version 1
class Solution:def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:candidates = set([source])count = 0while candidates:if target in candidates:return countcount += 1temp = set()for cand in candidates:indices = []for index, route in enumerate(routes):if cand in route:temp |= set(route)indices.append(index)for i in indices[::-1]:routes.pop(i)candidates = tempreturn -1
- Version 2
class Solution:def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:# stat = {}# for route in routes:# for stop in route:# stat[stop] = stat.get(stop, 0) + 1stat = collections.Counter([x for route in routes for x in route])transfers = []for route in routes:temp = []for stop in route:if stat[stop] > 1 or stop == source or stop == target:temp.append(stop)if len(temp) > 0:transfers.append(temp)candidates = set([source])count = 0while candidates:if target in candidates:return countcount += 1temp = set()for cand in candidates:indices = []for index, route in enumerate(transfers):if cand in route:temp |= set(route)indices.append(index)for i in indices[::-1]:transfers.pop(i)candidates = tempreturn -1
Reference
- https://leetcode.com/problems/bus-routes/