## Shortest Path Visiting All Nodes

• Time:O(2^n \cdot n)
• Space:O(2^n \cdot n)

## C++

class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
const int n = graph.size();
const int goal = (1 << n) - 1;

int ans = 0;
queue<pair<int, int>> q;  // (u, state)
vector<vector<bool>> seen(n, vector<bool>(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;
}
};


## JAVA

class Solution {
public int shortestPathLength(int[][] graph) {
final int n = graph.length;
final int goal = (1 << n) - 1;

int ans = 0;
Queue<Pair<Integer, Integer>> 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;
}
}


## Python

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