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.

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

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.