leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0847.cpp (771B)

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 };