# Min Cost to Visit Every Node - Dynamic Programming / Bitmask

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.

Explained nicely in this video: https://www.youtube.com/watch?v=iQBxxTZDajU

Implemented with necessary details

``````int dfs(int bitmaskPath, int cur, vector<vector<int>> & graph, vector<vector<int>> &dp) {
int nbits = (1 << graph.size()) - 1;
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));
}
}
}

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.

Great video! But I think that problem has some key differences from this one (undirected, connected, may revisit nodes)