Min Cost to Visit Every Node - Dynamic Programming / Bitmask

Problems
1

https://algo.monster/problems/min_cost_to_visit_every_node

2

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.

3

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

4

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;
}
5

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?

6

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.

7

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

8

The problem should specify we are visiting each node once. Otherwise, the solution doesn’t work for a graph like

[
[0, 1, 1],
[1, 0, 0],
[1, 0, 0]
]

If we are allowed to visit a node more than once, there is a solution with 1->2->1->3. Otherwise there isn’t.