leetcode

0 class Solution {

1 bool seen[12][1 << 12] = { 0 };

2

3 public:

4 int shortestPathLength(const vector<vector<int>>& graph) {

5 const int n = graph.size(), goal = (1 << n) - 1;

6

7 queue<tuple<int,int,int>> q;

8 for(int i = 0; i < n; i++) {

9 q.push({i, 1 << i, 0});

10 seen[i][1 << i] = true;

11 }

12

13 while (!q.empty()) {

14 const auto [idx, mask, dist] = q.front(); q.pop();

15

16 if(mask == goal) return dist;

17 for(const auto v: graph[idx]) {

18 const int mask_v = mask | 1 << v;

19 if(!seen[v][mask_v]) {

20 q.push({v, mask_v, dist+1});

21 seen[v][mask_v] = true;

22 }

23 }

24 }

25

26 return 0;

27 }

28 };