本文主要是介绍***Leetcode 847. Shortest Path Visiting All Nodes | 状压dp+dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/
非常不错的题，状压dp，state表示已经去过哪些。
一个非常重要的剪枝是，如果一个结点的出度是x，那么如果现在是第x+1次访问这个结点，就必然是重复状态
int dp[ (1<<13)+10 ][ 13 ];int MX = INT_MAX/3;class Solution {
public:int shortestPathLength(vector<vector<int> >& graph) {int last_state = (1<<graph.size()) - 1;des = last_state;for (int i = 0; i < (1<<graph.size()); i++) {for (int j = 0; j < graph.size(); j++) {dp[i][j] = (i == last_state? 0 : MX);}}int ans = MX;for (int i = 0; i < graph.size(); i++) {vector<int>vcnt(graph.size(), 0);ans = min( ans, dfs((1<<i), i, graph, i, vcnt) );} return ans;}int dfs(int state, int pos, vector< vector<int> > & graph, int st, vector<int>&vcnt ) {if ( state == des ) {return dp[state][pos] = 0;}if (dp[state][pos] != MX) {return dp[state][pos];}int ret = MX;for (int j = 0; j < graph[pos].size(); j++) {int to = graph[pos][j];int tmp = state | (1<<to);if (state == tmp && vcnt[to] >= graph[to].size()) continue;vcnt[pos] ++;ret = min(ret, dfs(tmp, to, graph, st, vcnt) + 1 );vcnt[pos] --;}return dp[state][pos] = ret;}int des;};
这篇关于***Leetcode 847. Shortest Path Visiting All Nodes | 状压dp+dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
