文章作者：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 = 0
while candidates:
if target in candidates:
return count
count = 1
temp = 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 = temp
return -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) 1
stat = 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 = 0
while candidates:
if target in candidates:
return count
count = 1
temp = 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 = temp
return -1Reference
- https://leetcode.com/problems/bus-routes/
