## 题目描述：

LeetCode 815. Bus Routes

We have a list of bus routes. Each `routes[i]` is a bus route that the i-th bus repeats forever. For example if `routes[0] = [1, 5, 7]`, this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop `S` (initially not on a bus), and we want to go to bus stop `T`. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

```Example:
Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
```

Note:

• `1 <= routes.length <= 500`.
• `1 <= routes[i].length <= 500`.
• `0 <= routes[i][j] < 10 ^ 6`.

## 解题思路：

```根据车站对公交车进行分组，记为stopBuses

## Python代码：

``````class Solution(object):
def numBusesToDestination(self, routes, S, T):
"""
:type routes: List[List[int]]
:type S: int
:type T: int
:rtype: int
"""
busNexts = collections.defaultdict(set)
stopBuses = collections.defaultdict(set)
for bus, stops in enumerate(routes):
for stop in stops:
for buses in stopBuses.values():
for bus in buses:
busNexts[bus] |= set(buses)

q = stopBuses[S]
vset = set(q)
ans = 0
found = False
q0 = []
for s in q:
if s in stopBuses[T]:
found = True
break
for n in busNexts[s]:
if n not in vset:
q0.append(n)
q = q0
ans += 1
return 0 if S == T else ans if found else -1
``````

Pingbacks已关闭。