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

糖逗

题目描述：

给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。 

graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

 

示例 1：

输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]
示例 2：

输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一个可能的路径为 [0,1,4,2,3]
 

提示：

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
private:
    struct State{
        int visited_state;
        int cur_index;
        State(int visited_state, int cur_index): visited_state(visited_state), cur_index(cur_index){}
    };
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int N = graph.size();
        vector<vector<bool> >store_state(1 << N, vector<bool>(N, false));//N个节点共有2^N个状态
        //确定结束状态
        int end = (1 << N) - 1;
        queue<State> store;
        //分别以每个节点为初始点，开始遍历
        for(int i = 0; i < N; i++){
            State cur(1 << i, i);
            store.push(cur);
        }
        //广度优先搜索
        int res = 0;
        while(!store.empty()){
            int temp = store.size();
            for(int i = 0; i < temp; i++){
                State temp1 = store.front();
                store.pop();
                int visit = temp1.visited_state;
                int cur = temp1.cur_index;
                if(visit == end){
                    return res;
                }
                for(auto next_index : graph[cur]){
                    int next_visited = (visit | (1 << next_index));
                    if(store_state[next_visited][next_index] == false){
                        store.push(State(next_visited, next_index));
                        store_state[next_visited][next_index] = true;
                    }
                }
            }
            res++;
        }
        return -1;
    }
};

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

糖逗

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