Skip to content

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

    for (int step = 0; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [u, state] = q.front();
        q.pop();
        if (state == goal)
          return step;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (const int v : graph[u])
          q.emplace(v, state | 1 << v);
      }

    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
class Solution {
  public int shortestPathLength(int[][] graph) {
    final int n = graph.length;
    final int goal = (1 << n) - 1;
    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));

    for (int step = 0; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.peek().getKey();
        final int state = q.poll().getValue();
        if (state == goal)
          return step;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (final int v : graph[u])
          q.offer(new Pair<>(v, state | 1 << v));
      }

    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
class Solution:
  def shortestPathLength(self, graph: list[list[int]]) -> int:
    n = len(graph)
    goal = (1 << n) - 1
    q = collections.deque()  # (u, state)
    seen = set()

    for i in range(n):
      q.append((i, 1 << i))

    step = 0
    while q:
      for _ in range(len(q)):
        u, state = q.popleft()
        if state == goal:
          return step
        if (u, state) in seen:
          continue
        seen.add((u, state))
        for v in graph[u]:
          q.append((v, state | 1 << v))
      step += 1

    return -1