# 847. Shortest Path Visiting All Nodes

• Time: $O(2^n \cdot n)$
• Space: $O(2^n \cdot n)$
  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 class Solution { public: int shortestPathLength(vector>& graph) { const int n = graph.size(); const int goal = (1 << n) - 1; int ans = 0; queue> q; // (u, state) vector> seen(n, vector(1 << n)); for (int i = 0; i < n; ++i) q.emplace(i, 1 << i); while (!q.empty()) { for (int sz = q.size(); sz > 0; --sz) { const auto [u, state] = q.front(); q.pop(); if (state == goal) return ans; if (seen[u][state]) continue; seen[u][state] = true; for (const int v : graph[u]) q.emplace(v, state | (1 << v)); } ++ans; } return -1; } }; 
  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 class Solution { public int shortestPathLength(int[][] graph) { final int n = graph.length; final int goal = (1 << n) - 1; int ans = 0; Queue> q = new ArrayDeque<>(); // (u, state) boolean[][] seen = new boolean[n][1 << n]; for (int i = 0; i < n; ++i) q.offer(new Pair<>(i, 1 << i)); while (!q.isEmpty()) { for (int sz = q.size(); sz > 0; --sz) { final int u = q.peek().getKey(); final int state = q.poll().getValue(); if (state == goal) return ans; if (seen[u][state]) continue; seen[u][state] = true; for (final int v : graph[u]) q.offer(new Pair<>(v, state | (1 << v))); } ++ans; } return -1; } } 
  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 class Solution: def shortestPathLength(self, graph: List[List[int]]) -> int: n = len(graph) goal = (1 << n) - 1 ans = 0 q = deque() # (u, state) seen = set() for i in range(n): q.append((i, 1 << i)) while q: for _ in range(len(q)): u, state = q.popleft() if state == goal: return ans if (u, state) in seen: continue seen.add((u, state)) for v in graph[u]: q.append((v, state | (1 << v))) ans += 1 return -1