# [LeetCode] 815. Bus Routes 公交路线

2021年09月15日 阅读数：2

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.html

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.java

```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:python

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

Java:post

```class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
HashSet<Integer> visited = new HashSet<>();
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
int ret = 0;

if (S==T) return 0;

for(int i = 0; i < routes.length; i++){
for(int j = 0; j < routes[i].length; j++){
ArrayList<Integer> buses = map.getOrDefault(routes[i][j], new ArrayList<>());
map.put(routes[i][j], buses);
}
}

q.offer(S);
while (!q.isEmpty()) {
int len = q.size();
ret++;
for (int i = 0; i < len; i++) {
int cur = q.poll();
ArrayList<Integer> buses = map.get(cur);
for (int bus: buses) {
if (visited.contains(bus)) continue;
for (int j = 0; j < routes[bus].length; j++) {
if (routes[bus][j] == T) return ret;
q.offer(routes[bus][j]);
}
}
}
}
return -1;
}
}　　```

Java:this

```public int numBusesToDestination(int[][] routes, int S, int T) {
HashMap<Integer, HashSet<Integer>> to_routes = new HashMap<>();
for (int i = 0; i < routes.length; ++i)
for (int j : routes[i]) {
if (!to_routes.containsKey(j)) to_routes.put(j, new HashSet<Integer>());
}
Queue<Point> bfs = new ArrayDeque();
bfs.offer(new Point(S, 0));
HashSet<Integer> seen = new HashSet<>();
while (!bfs.isEmpty()) {
int stop = bfs.peek().x, bus = bfs.peek().y;
bfs.poll();
if (stop == T) return bus;
for (int route_i : to_routes.get(stop))
for (int next_stop : routes[route_i])
if (!seen.contains(next_stop)) {
bfs.offer(new Point(next_stop, bus + 1));
}
}
return -1;
}
```

Python:url

```def numBusesToDestination(self, routes, S, T):
to_routes = collections.defaultdict(set)
for i,route in enumerate(routes):
bfs = [(S,0)]
seen = set([S])
for stop, bus in bfs:
if stop == T: return bus
for route_i in to_routes[stop]:
for next_stop in routes[route_i]:
if next_stop not in seen:
bfs.append((next_stop, bus+1))
routes[route_i] = []
return -1
```

Python:code

```# Time:  O(|V| + |E|)
# Space: O(|V| + |E|)

import collections

class Solution(object):
def numBusesToDestination(self, routes, S, T):
"""
:type routes: List[List[int]]
:type S: int
:type T: int
:rtype: int
"""
if S == T:
return 0

to_route = collections.defaultdict(set)
for i, route in enumerate(routes):
for stop in route:

result = 1
q = [S]
lookup = set([S])
while q:
next_q = []
for stop in q:
for i in to_route[stop]:
for next_stop in routes[i]:
if next_stop in lookup:
continue
if next_stop == T:
return result
next_q.append(next_stop)
to_route[next_stop].remove(i)
q = next_q
result += 1

return -1　　```

C++:htm

```int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
unordered_map<int, unordered_set<int>> to_route;
for (int i = 0; i < routes.size(); ++i) for (auto& j : routes[i]) to_route[j].insert(i);
queue<pair<int, int>> bfs; bfs.push(make_pair(S, 0));
unordered_set<int> seen = {S};
while (!bfs.empty()) {
int stop = bfs.front().first, bus = bfs.front().second;
bfs.pop();
if (stop == T) return bus;
for (auto& route_i : to_route[stop]) {
for (auto& next_stop : routes[route_i])
if (seen.find(next_stop) == seen.end()) {
seen.insert(next_stop);
bfs.push(make_pair(next_stop, bus + 1));
}
routes[route_i].clear();
}
}
return -1;
}
```