leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0847.cpp (771B)

      1 class Solution {
      2     bool seen[12][1 << 12] = { 0 };
      3 
      4 public:
      5     int shortestPathLength(const vector<vector<int>>& graph) {
      6         const int n = graph.size(), goal = (1 << n) - 1;
      7 
      8         queue<tuple<int,int,int>> q;
      9         for(int i = 0; i < n; i++) {
     10             q.push({i, 1 << i, 0});
     11             seen[i][1 << i] = true;
     12         }
     13 
     14         while (!q.empty()) {
     15             const auto [idx, mask, dist] = q.front(); q.pop();
     16 
     17             if(mask == goal) return dist;
     18             for(const auto v: graph[idx]) {
     19                 const int mask_v = mask | 1 << v;
     20                 if(!seen[v][mask_v]) {
     21                     q.push({v, mask_v, dist+1});
     22                     seen[v][mask_v] = true;
     23                 }
     24             }
     25         }
     26 
     27         return 0;
     28     }
     29 };