1
class Solution {
2
  class Pair {
3
    int i;
4
    int path;
5

6
    public Pair(int i, int path) {
7
      this.i = i;
8
      this.path = path;
9
    }
10
  }
11

12
  public int shortestPathLength(int[][] graph) {
13
    /*
14
    For each node currentNode, steps as key, visited as value
15
    boolean[currentNode][steps]
16
    */
17
    int n = graph.length;
18

19
    // 111....1, 1<< n - 1
20
    int allVisited = (1 << n) - 1;
21

22
    boolean[][] visited = new boolean[n][1 << n];
23
    Queue<Pair> q = new LinkedList<>();
24
    for (int i = 0; i < n; i++) {
25
      if (1 << i == allVisited) return 0;
26
      visited[i][1 << i] = true;
27
      q.offer(new Pair(i, 1 << i));
28
    }
29
    int step = 0;
30
    while (!q.isEmpty()) {
31
      int size = q.size();
32
      for (int i = 0; i < size; i++) {
33
        Pair p = q.poll();
34
        int[] edges = graph[p.i];
35

36
        for (int t : edges) {
37
          int path = p.path | (1 << t);
38
          if (path == allVisited) return step + 1;
39
          if (!visited[t][path]) {
40
            visited[t][path] = true;
41
            q.offer(new Pair(t, path));
42
          }
43
        }
44
      }
45
      step++;
46
    }
47
    return step;
48
  }
49
}