Algorithm
Problem Name: 815. Bus Routes
Problem Link: https://leetcode.com/problems/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 the0thbus 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) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if (S == T) {
return 0;
}
unordered_map < int, vector<int>>m(501); // Stop to Bus
int n = routes.size();
// Build graph Stop-to-Bus
for (int i = 0; i < n; ++i) {
for (int j = 0; j < routes[i].size(); ++j) {
m[routes[i][j]].push_back(i);
}
}
vector<int>visitedBus(501);
vector<int>visitedStop(1000001);
// BFS
queue < int>cur;
queue<int>next;
for (int& b: m[S]) {
cur.push(b);
}
int count = 1;
while (!cur.empty()) {
int bus = cur.front();
cur.pop();
visitedBus[bus] = 1;
for (int& s: routes[bus]) {
if (s == T) {
return count;
}
if (visitedStop[s]) {
continue;
}
visitedStop[s] = 1;
for (int& b: m[s]) {
if (!visitedBus[b]) {
next.push(b);
}
}
}
if (cur.empty()) {
++count;
swap(cur, next);
}
}
return -1;
}
};
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output
2
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numBusesToDestination = function (routes, S, T) {
if (S === T) return 0
const map = {}
const visited = new Array(routes.length).fill(false),
queue = [S]
let rides = 0
for (let i = 0; i < routes.length; i++) {
for (const stop of routes[i]) {
if (map[stop] === undefined) {
map[stop] = []
}
map[stop].push(i)
}
}
while (queue.length > 0) {
let size = queue.length
rides += 1
while (size > 0) {
const currStop = queue.shift()
size -= 1
for (const bus of map[currStop]) {
if (visited[bus]) continue
visited[bus] = true
for (const stop of routes[bus]) {
if (stop === T) return rides
queue.push(stop)
}
}
}
}
return -1
}
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output
2
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numBusesToDestination(self, routes, starterBus, targetBus):
path, travel, travelTaken, used = collections.defaultdict(set), [starterBus], 0, set()
for i, route in enumerate(routes):
for bus in route:
path[bus].add(i)
while travel:
new = []
for bus in travel:
if bus == targetBus:
return travelTaken
for route in path[bus]:
if route not in used:
used.add(route)
for nextBus in routes[route]:
if nextBus != bus:
new.append(nextBus)
travelTaken += 1
travel = new
return -1
Input
routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output
-1