Before looking at the solution, it would be good to research more about the problem and checkout the regular DP solution. Bitmask is cool though.
Implemented with necessary details
int dfs(int bitmaskPath, int cur, vector<vector<int>> & graph, vector<vector<int>> &dp) {
int nbits = (1 << graph.size()) - 1;
if(bitmaskPath == nbits) return 0;
if(dp[bitmaskPath][cur] != 0) return dp[bitmaskPath][cur];
int ans = INF;
for(int i = 0; i < graph[cur].size(); i++){
int visitedPath = bitmaskPath & 1 << i;
if(visitedPath == 0 && graph[cur][i]) {
int nextbits = bitmaskPath | (1 << i);
ans = min(ans, graph[cur][i] + dfs(nextbits, i, graph, dp));
}
}
return dp[bitmaskPath][cur] = ans;
}
int min_cost_to_visit_every_node(std::vector<std::vector<int>> graph) {
// WRITE YOUR BRILLIANT CODE HERE
int m = graph.size();
//return bfs(graph);
int bitmask = 1 << 0;
vector<vector<int>> dp(1 << m, vector<int> (m, 0));
int ans = dfs(bitmask, 0, graph, dp);
return ans == INF ? -1 : ans;
}
Test Case#6, I can find path:
0->2->4->3->1->3->7->5->9->4->8->2->6
and get cost 1230 smaller than expected output 1328.
Could anyone verify or explain?
I didn’t check the costs but your path is visiting node 3 twice. The Traveling Salesman problem asks for visiting each node exactly once. This should be better explained in the problem statement.