<filename>src/q_801_850/q0847.cc
#include <gtest/gtest.h>
#include <iostream>
#include <vector>

using namespace std;

/**
 * This file is generated by leetcode_add.py
 *
 * 847.
 *      Shortest Path Visiting All Nodes
 *
 * ––––––––––––––––––––––––––––– Description –––––––––––––––––––––––––––––
 *
 *   You have an undirected, connected graph of ‘n’ nodes labeled from ‘0’
 *   to ‘n - 1’ . You are given an array ‘graph’ where ‘graph[i]’ is a list
 *   of all the nodes connected with node ‘i’ by an
 *   Return “the length of the shortest path that visits every node” . You
 *   may start and stop at any node, you may revisit nodes multiple times,
 *   and you may reuse edges.
 *
 * ––––––––––––––––––––––––––––– Constraints –––––––––––––––––––––––––––––
 *
 *   • ‘n = graph.length’
 *   • ‘1 ≤ n ≤ 12’
 *   • ‘0 ≤ graph[i].length <n’
 *   • ‘graph[i]’ does not contain ‘i’ .
 *   • If ‘graph[a]’ contains ‘b’ , then ‘graph[b]’ contains ‘a’ .
 *   • The input graph is always connected.
 *
 */

struct q847 : public ::testing::Test {
  // Leetcode answer here
  class Solution {
   private:
    vector<vector<int>> graph;
    vector<vector<int>> cache = vector<vector<int>>(13, vector<int>(1 << 13, 0));

    int shortest(int from, int mask) {
      if (cache[from][mask] != 0) {
        return cache[from][mask];
      }

      if ((mask & (mask - 1)) == 0) {
        return 0;
      }

      cache[from][mask] = numeric_limits<int>::max() - 1;

      for (auto &node : graph[from]) {
        if ((mask & (1 << node)) == 0) continue;
        int already_visited = cache[node][mask] != 0
                                  ? cache[node][mask]
                                  : shortest(node, mask);

        int not_visited = cache[node][mask ^ (1 << from)] != 0
                              ? cache[node][mask ^ (1 << from)]
                              : shortest(node, mask ^ (1 << from));

        cache[from][mask] = min(cache[from][mask],
                                1 + min(already_visited, not_visited));
      }

      return cache[from][mask];
    }

   public:
    int shortestPathLength(vector<vector<int>> &graph) {
      int res = numeric_limits<int>::max(),
          n = graph.size(),
          end_mask = (1 << n) - 1;

      this->graph = move(graph);

      for (int i = 0; i < n; ++i) {
        res = min(res, shortest(i, end_mask));
      }

      graph = move(this->graph);

      return res;
    }
  };

  class Solution *solution;
};

TEST_F(q847, sample_input01) {
  solution = new Solution();
  vector<vector<int>> graph = {{1, 2, 3}, {0}, {0}, {0}};
  int exp = 4;
  int act = solution->shortestPathLength(graph);
  EXPECT_EQ(act, exp);
  delete solution;
}

TEST_F(q847, sample_input02) {
  solution = new Solution();
  vector<vector<int>> graph = {{1}, {0, 2, 4}, {1, 3, 4}, {2}, {1, 2}};
  int exp = 4;
  int act = solution->shortestPathLength(graph);
  EXPECT_EQ(act, exp);
  delete solution;
}