leetcode

commit 484afbc6e24acf0ca7e8a058b666a966afb020aa
parent 93006a9396d50b98bb40a900b0278244d74cb45b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 12 Nov 2023 20:04:17 +0000

Improved Daily Problem

Diffstat:
M
Problems/0815.cpp
 | 
25
+++++++++++++++----------

1 file changed, 15 insertions(+), 10 deletions(-)
diff --git a/Problems/0815.cpp b/Problems/0815.cpp
@@ -1,29 +1,34 @@
 class Solution {
   public:
-    int numBusesToDestination(vector<vector<int>> &routes, int source, int target) {
+    int numBusesToDestination(const vector<vector<int>> &routes, int source, int target) const {
         if (source == target) return 0;
 
         unordered_map<int, vector<int>> adj;
-        queue<int> q;
+        for (int i = 0; i < routes.size(); i++) {
+            for (const int n : routes[i])
+                adj[n].push_back(i);
+        }
 
-        for (int i = 0; i < routes.size(); i++)
-            for (auto s : routes[i])
-                adj[s].push_back(i);
         if (!adj.count(target)) return -1;
 
+        unordered_set<int> used;
+        queue<int> q;
+
         q.push(source);
         for (int lvl = 1; !q.empty(); lvl++) {
             for (int k = q.size(); k > 0; k--) {
-                int crnt = q.front();
+                const int crnt = q.front();
                 q.pop();
-                for (int r : adj[crnt]) {
-                    for (int v : routes[r]) {
+                for (const int r : adj[crnt]) {
+                    if (used.count(-r)) continue;
+                    used.insert(-r);
+                    for (const int v : routes[r]) {
+                        if (used.count(v)) continue;
                         if (v == target) return lvl;
+                        used.insert(v);
                         q.push(v);
                     }
-                    routes[r].clear();
                 }
-                adj[crnt].clear();
             }
         }