C++刷leetcode（847. 访问所有节点的最短路径）【状态压缩】【广度优先搜索】
题目描述：给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。
graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph 中恰好出现一次。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 1：
输入：[,,,]
输出：4
解释：一个可能的路径为
示例 2：
输入：[,,,,]
输出：4
解释：一个可能的路径为
提示：
1 <= graph.length <= 12
0 <= graph.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){
int next_visited = (visit | (1 << next_index));
if(store_state == false){
store.push(State(next_visited, next_index));
store_state = true;
}
}
}
res++;
}
return -1;
}
};
状态压缩参考：https://www.bilibili.com/video/BV1gt4y1U72F?from=search&seid=15698129737800543270
代码参考：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/solution/bfszhuang-tai-ya-suo-by-hardcoding/ 过年后就好久没发帖了{:10_262:}学起来！
页:
[1]