leetcode

commit 139d1e6bd32f6003fb80e9af1e7cedbbbe0b043e
parent d250236243ac338a7918fcea8415b6582353071b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 14 Feb 2023 15:14:27 +0100

LeetCode 75 II: Day 11

Diffstat:
A
Problems/0815.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0815.cpp b/Problems/0815.cpp
@@ -0,0 +1,32 @@
+class Solution {
+public:
+  int numBusesToDestination(vector<vector<int>> &routes, int source,
+                            int target) {
+    if (source == target) return 0;
+
+    unordered_map<int, vector<int>> adj;
+    queue<int> q;
+
+    for (int i = 0; i < routes.size(); i++)
+      for (auto s : routes[i]) adj[s].push_back(i);
+    if (!adj.count(target)) return -1;
+
+    q.push(source);
+    for (int lvl = 1; !q.empty(); lvl++) {
+      for (int k = q.size(); k > 0; k--) {
+        int crnt = q.front();
+        q.pop();
+        for (int r : adj[crnt]) {
+          for (int v : routes[r]) {
+            if (v == target) return lvl;
+            q.push(v);
+          }
+          routes[r].clear();
+        }
+        adj[crnt].clear();
+      }
+    }
+
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -288,6 +288,7 @@ for solving problems.
 |  0787  |   Medium   | [Cheapest Flights Within K Stops](Problems/0787.cpp)                                             |
 |  0797  |   Medium   | [All Paths From Source to Target](Problems/0797.cpp)                                             |
 |  0802  |   Medium   | [Find Eventual Safe States](Problems/0802.cpp)                                                   |
+|  0815  |    Hard    | [Bus Routes](Problems/0815.cpp)                                                                  |
 |  0830  |   Medium   | [Kth Smallest Element in a BST](Problems/0230.cpp)                                               |
 |  0841  |   Medium   | [Keys and Rooms](Problems/0841.cpp)                                                              |
 |  0844  |    Easy    | [Backspace String Compare](Problems/0844.cpp)                                                    |