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.
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.
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:
-
1 <= routes.length <= 500. -
1 <= routes[i].length <= 500. -
0 <= routes[i][j] < 10 ^ 6.
我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->... 的车站路线行驶。
假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。
示例: 输入: routes = [[1, 2, 7], [3, 6, 7]] S = 1 T = 6 输出: 2 解释: 最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。
说明:
-
1 <= routes.length <= 500. -
1 <= routes[i].length <= 500. -
0 <= routes[i][j] < 10 ^ 6.
584ms
1 class Solution {
2 // BFS is easier, also faster
3 func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
4 if S == T { return 0 }
5 var stopToRoutes = [Int: [Int]]()
6 for (index, route) in routes.enumerated() {
7 for stop in route {
8 if var buses = stopToRoutes[stop] {
9 buses.append(index)
10 stopToRoutes[stop] = buses
11 } else {
12 stopToRoutes[stop] = [index]
13 }
14 }
15 }
16
17 //print(stopToRoutes)
18
19 var queue = [Int]()
20 queue.append(S)
21 var visited = Set<Int>()
22 var ans = 0
23 while (!queue.isEmpty) {
24 //print(queue, visited, ans)
25 ans += 1
26 var size = queue.count
27 while (size > 0) {
28 let last = queue.remove(at: 0)
29 for route in (stopToRoutes[last] ?? []) {
30 if visited.contains(route) {
31 continue
32 } else {
33 visited.insert(route)
34 }
35 for stop in routes[route] {
36 if stop == T {
37 return ans
38 }
39 queue.append(stop)
40 }
41 }
42 size -= 1
43 }
44 }
45 return -1
46 }
47
48 // LTE
49 // graph search: DFS
50 func numBusesToDestination1(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
51 if S == T { return 0 }
52 var stopToRoutes = [Int: [Int]]()
53 for (index, route) in routes.enumerated() {
54 for stop in route {
55 if var buses = stopToRoutes[stop] {
56 buses.append(index)
57 stopToRoutes[stop] = buses
58 } else {
59 stopToRoutes[stop] = [index]
60 }
61 }
62 }
63 print(stopToRoutes)
64
65 var startI = stopToRoutes[S] ?? []
66 var targetI = stopToRoutes[T] ?? []
67 var ret = Int.max
68 var routes = routes
69 for si in startI {
70 var visited = Set<Int>()
71 find(&routes, &stopToRoutes, si, targetI, &visited, 1, &ret)
72 }
73 return ret > routes.count ? -1: ret
74 }
75
76 private func find(_ routes: inout [[Int]], _ map: inout [Int: [Int]], _ curi: Int, _ ei: [Int], _ visited: inout Set<Int>, _ curStops: Int, _ ret: inout Int) {
77 if ei.contains(curi) {
78 ret = min(ret, curStops)
79 return
80 }
81 if visited.contains(curi) {
82 return
83 }
84 visited.insert(curi)
85
86 let stops = routes[curi]
87 for stop in stops {
88 let buses = map[stop] ?? []
89 for route in buses {
90 //print("find",curi, ei, stop, route, curStops)
91
92 find(&routes, &map, route, ei, &visited, curStops + 1, &ret)
93 }
94 }
95
96 visited.remove(curi)
97 }
98 }
Runtime: 604 ms Memory Usage: 24.5 MB
1 class Solution {
2 func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
3 if S == T {return 0}
4 var res:Int = 0
5 var stop2bus:[Int:[Int]] = [Int:[Int]]()
6 var q:[Int] = [S]
7 var visited:Set<Int> = Set<Int>()
8 for i in 0..<routes.count
9 {
10 for j in routes[i]
11 {
12 stop2bus[j,default:[Int]()].append(i)
13 }
14 }
15 while(!q.isEmpty)
16 {
17 res += 1
18 for i in stride(from:q.count,to:0,by:-1)
19 {
20 var t:Int = q.removeFirst()
21 for bus in stop2bus[t,default:[Int]()]
22 {
23 if visited.contains(bus) {continue}
24 visited.insert(bus)
25 for stop in routes[bus]
26 {
27 if stop == T {return res}
28 q.append(stop)
29 }
30 }
31 }
32 }
33 return -1
34 }
35 }
644ms
1 class Solution {
2 func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
3 var visited: Set<Int> = []
4 var queue: [Int] = []
5 var map: [Int: [Int]] = [:]
6 var steps = 0
7
8 if S == T {
9 return 0
10 }
11
12 for i in 0 ..< routes.count {
13 for j in 0 ..< routes[i].count {
14 if map[routes[i][j]] == nil {
15 map[routes[i][j]] = []
16 }
17
18 map[routes[i][j]]!.append(i)
19 }
20 }
21
22 queue.append(S)
23
24 while !queue.isEmpty {
25 var size = queue.count
26 steps += 1
27 while size > 0 {
28 let curr = queue.removeFirst()
29 let buses = map[curr]!
30 for bus in buses {
31 if !visited.contains(bus) {
32 visited.insert(bus)
33 for j in 0 ..< routes[bus].count {
34 if routes[bus][j] == T {
35 return steps
36 }
37 queue.append(routes[bus][j])
38 }
39 }
40 }
41 size -= 1
42 }
43 }
44
45 return -1
46 }
47 }
1360ms
1 class Solution {
2 func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
3 var stops: [Int: [Int]] = [:]
4 for (bus, route) in routes.enumerated() {
5 for stop in route {
6 stops[stop, default: []].append(bus)
7 }
8 }
9 var res = 0
10 var queue: [Int] = []
11 queue.append(S)
12 var visitedStops: Set<Int> = []
13 var visitedBuses: Set<Int> = []
14 while queue.isEmpty == false {
15 var n = queue.count
16 while n > 0 {
17 n -= 1
18 let cur = queue.removeFirst()
19 if cur == T {
20 return res
21 }
22 if visitedStops.contains(cur) {
23 continue
24 }
25 visitedStops.insert(cur)
26 for bus in (stops[cur] ?? []) {
27 if visitedBuses.contains(bus) == true {
28 continue
29 }
30 visitedBuses.insert(bus)
31 for stop in routes[bus] {
32 queue.append(stop)
33 }
34 }
35 }
36 res += 1
37 }
38 return -1
39 }
40 }