[leetcode] 847. Shortest Path Visiting All Nodes : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

[fail-TSP]Shortest Path Visiting All Nodes.cc

class Solution {
public:
    int MAX = 100;
	int len = 0;
	vector<vector<int>> d = vector<vector<int>>();
	vector<vector<int>> adj = vector<vector<int>>();

	int TSP(int now, int visit) {

		visit |= (1 << now);

		if (visit == (1 << len) - 1)
			return 0;

		int& ret = d[visit][now];

		//memorization
		if (ret > 0)
			return ret;
		ret = 100;

		for (int i = 0; i<adj[now].size(); i++) {
			int next = adj[now][i];
		    ret = min(ret, TSP(next, visit) + 1);
		}
		return ret;
	}

	int shortestPathLength(vector<vector<int>>& graph) {
		//initialize
		len = graph.size();
		adj = graph;
		
		//solve -> with DP
		int ans = 100;
		for (int i = 0; i < len; i++) {
		    d.clear();
            d.resize(1 << len, vector<int>(len, -1));
			ans = min(TSP(i, 0), ans);
		}

		return ans;
	}
};