1
class Solution {
2
 public:
3
  int shortestPathLength(vector<vector<int>> &graph) {
4
    int n = graph.size();
5
    string mask = "";
6
    string eq = "";
7
    for (int i = 0; i < n; i++) {
8
      mask += '0';
9
      eq += '1';
10
    }
11
    queue<pair<int, string>> q;
12
    set<pair<int, string>> s;
13
    for (int i = 0; i < n; i++) {
14
      string temp = mask;
15
      temp[i] = '1';
16
      q.push({i, temp});
17
      s.insert({i, temp});
18
    }
19
    int c = 0;
20
    int flag = 0;
21
    while (!q.empty()) {
22
      int size = q.size();
23
      for (int i = 0; i < size; i++) {
24
        auto top = q.front();
25
        q.pop();
26
        if (top.second == eq) return c;
27
        for (auto p : graph[top.first]) {
28
          string temp1 = top.second;
29
          temp1[p] = '1';
30
          if (s.count({p, temp1}) == 0) {
31
            q.push({p, temp1});
32
            s.insert({p, temp1});
33
          }
34
        }
35
      }
36
      c++;
37
      cout << "c is " << c;
38
    }
39
    return -1;
40
  }
41
};