leetcode

commit 94271d7e360bf8d7acb91178c5096d79b67b6a9f
parent 0f2cc3f9f728a5d2bc1aa3d3046f265b01bcb9d3
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 17 Sep 2023 21:16:38 +0000

Daily Problem

Diffstat:
A
Problems/0847.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/0847.cpp b/Problems/0847.cpp
@@ -0,0 +1,29 @@
+class Solution {
+    bool seen[12][1 << 12] = { 0 };
+
+public:
+    int shortestPathLength(const vector<vector<int>>& graph) {
+        const int n = graph.size(), goal = (1 << n) - 1;
+
+        queue<tuple<int,int,int>> q;
+        for(int i = 0; i < n; i++) {
+            q.push({i, 1 << i, 0});
+            seen[i][1 << i] = true;
+        }
+
+        while (!q.empty()) {
+            const auto [idx, mask, dist] = q.front(); q.pop();
+
+            if(mask == goal) return dist;
+            for(const auto v: graph[idx]) {
+                const int mask_v = mask | 1 << v;
+                if(!seen[v][mask_v]) {
+                    q.push({v, mask_v, dist+1});
+                    seen[v][mask_v] = true;
+                }
+            }
+        }
+
+        return 0;
+    }
+};
diff --git a/README.md b/README.md
@@ -399,6 +399,7 @@ for solving problems.
 |  0839  |    Hard    | [Similar String Groups](Problems/0839.cpp)                                                         |
 |  0841  |   Medium   | [Keys and Rooms](Problems/0841.cpp)                                                                |
 |  0844  |    Easy    | [Backspace String Compare](Problems/0844.cpp)                                                      |
+|  0847  |    Hard    | [Shortest Path Visiting All Nodes](Problems/0847.cpp)                                              |
 |  0851  |   Medium   | [Loud and Rich](Problems/0851.cpp)                                                                 |
 |  0852  |   Medium   | [Peak Index in a Mountain Array](Problems/0852.cpp)                                                |
 |  0853  |   Medium   | [Car Fleet](Problems/0853.cpp)                                                                     |