-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBus Routes.js
39 lines (31 loc) · 1.04 KB
/
Bus Routes.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var numBusesToDestination = function (routes, source, target) {
let stopRoutes = new Map();
for (let route = 0; route < routes.length; route++) {
for (let stop of routes[route]) {
if (!stopRoutes.has(stop)) stopRoutes.set(stop, new Set());
stopRoutes.get(stop).add(route);
}
}
let stopsToVisit = new Queue();
stopsToVisit.enqueue([source, 0]);
let visitedStops = new Set();
visitedStops.add(source);
let visitedRoutes = new Array(routes.length);
while (!stopsToVisit.isEmpty()) {
let stop = stopsToVisit.front()[0],
bus = stopsToVisit.front()[1];
stopsToVisit.dequeue();
if (stop === target) return bus;
for (let route of stopRoutes.get(stop)) {
if (visitedRoutes[route]) continue;
for (let stop of routes[route]) {
if (!visitedStops.has(stop)) {
visitedStops.add(stop);
stopsToVisit.enqueue([stop, bus + 1]);
}
}
visitedRoutes[route] = true;
}
}
return -1;
};