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 the0th
bus travels in the sequence1 -> 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.