## 815. Bus Routes

You are given an array `routes` representing bus routes where `routes[i]` is a bus route that the `ith` bus repeats forever.

• For example, if `routes[0] = [1, 5, 7]`, this means that the `0th` bus travels in the sequence `1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...` forever.

You will start at the bus stop `source` (You are not on any bus initially), and you want to go to the bus stop `target`. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from `source` to `target`. Return `-1` if it is not possible.

Example 1:

```Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 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.
```

Example 2:

```Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1
```

Constraints:

• `1 <= routes.length <= 500`.
• `1 <= routes[i].length <= 105`
• All the values of `routes[i]` are unique.
• `sum(routes[i].length) <= 105`
• `0 <= routes[i][j] < 106`
• `0 <= source, target < 106`

## Rust Solution

``````struct Solution;

use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
fn num_buses_to_destination(routes: Vec<Vec<i32>>, s: i32, t: i32) -> i32 {
if s == t {
return 0;
}
let mut buses: HashMap<i32, HashSet<usize>> = HashMap::new();
for i in 0..routes.len() {
for &j in &routes[i] {
buses.entry(j).or_default().insert(i);
}
}
let mut queue: VecDeque<i32> = VecDeque::new();
let mut visited: HashSet<usize> = HashSet::new();
queue.push_back(s);
let mut res = 0;
while !queue.is_empty() {
let size = queue.len();
for _ in 0..size {
let u = queue.pop_front().unwrap();
if u == t {
return res;
}
let mut stops = HashSet::new();
for &bus in &buses[&u] {
if visited.insert(bus) {
for &i in &routes[bus] {
stops.insert(i);
}
}
}
for stop in stops {
queue.push_back(stop);
}
}
res += 1;
}
-1
}
}

#[test]
fn test() {
let routes = vec_vec_i32![[1, 2, 7], [3, 6, 7]];
let s = 1;
let t = 6;
let res = 2;
assert_eq!(Solution::num_buses_to_destination(routes, s, t), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.