C++刷leetcode（847. 访问所有节点的最短路径）【状态压缩】【广度优先搜索】

糖逗

题目描述：

1. 给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。 
   
2. 
   
3. graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。
   
4. 
   
5. 返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：[[1,2,3],[0],[0],[0]]
    
12. 输出：4
    
13. 解释：一个可能的路径为 [1,0,2,0,3]
    
14. 示例 2：
    
15. 
    
16. 输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
    
17. 输出：4
    
18. 解释：一个可能的路径为 [0,1,4,2,3]
    
19.  
    
20. 
    
21. 提示：
    
22. 
    
23. 1 <= graph.length <= 12
    
24. 0 <= graph[i].length <&#160;graph.length
    
25. 
    
26. 来源：力扣（LeetCode）
    
27. 链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
    
28. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     struct State{
   
4.         int visited_state;
   
5.         int cur_index;
   
6.         State(int visited_state, int cur_index): visited_state(visited_state), cur_index(cur_index){}
   
7.     };
   
8. public:
   
9.     int shortestPathLength(vector<vector<int>>& graph) {
   
10.         int N = graph.size();
    
11.         vector<vector<bool> >store_state(1 << N, vector<bool>(N, false));//N个节点共有2^N个状态
    
12.         //确定结束状态
    
13.         int end = (1 << N) - 1;
    
14.         queue<State> store;
    
15.         //分别以每个节点为初始点，开始遍历
    
16.         for(int i = 0; i < N; i++){
    
17.             State cur(1 << i, i);
    
18.             store.push(cur);
    
19.         }
    
20.         //广度优先搜索
    
21.         int res = 0;
    
22.         while(!store.empty()){
    
23.             int temp = store.size();
    
24.             for(int i = 0; i < temp; i++){
    
25.                 State temp1 = store.front();
    
26.                 store.pop();
    
27.                 int visit = temp1.visited_state;
    
28.                 int cur = temp1.cur_index;
    
29.                 if(visit == end){
    
30.                     return res;
    
31.                 }
    
32.                 for(auto next_index : graph[cur]){
    
33.                     int next_visited = (visit | (1 << next_index));
    
34.                     if(store_state[next_visited][next_index] == false){
    
35.                         store.push(State(next_visited, next_index));
    
36.                         store_state[next_visited][next_index] = true;
    
37.                     }
    
38.                 }
    
39.             }
    
40.             res++;
    
41.         }
    
42.         return -1;
    
43.     }
    
44. };

复制代码

状态压缩参考：https://www.bilibili.com/video/B ... 5698129737800543270
代码参考：https://leetcode-cn.com/problems ... -suo-by-hardcoding/

糖逗

过年后就好久没发帖了学起来！