847. Shortest Path Visiting All Nodes

An undirected, connected graph of N nodes (labeled `0, 1, 2, ..., N-1`) is given as `graph`.

`graph.length = N`, and `j != i` is in the list `graph[i]` exactly once, if and only if nodes `i` and `j` are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

```Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]```

Example 2:

```Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
```

Note:

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

847. Shortest Path Visiting All Nodes
``````struct Solution;

use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
let n = graph.len();
.into_iter()
.map(|v| v.into_iter().map(|i| i as usize).collect())
.collect();
let mut visited: HashSet<(u32, usize)> = HashSet::new();
let mut queue: VecDeque<(u32, usize, i32)> = VecDeque::new();
for i in 0..n {
visited.insert((1 << i, i));
queue.push_back((1 << i, i, 0));
}
while let Some((bitset, i, d)) = queue.pop_front() {
if bitset == (1 << n) - 1 {
return d;
}
let next_bitset = bitset | (1 << j);
if visited.insert((next_bitset, j)) {
queue.push_back((next_bitset, j, d + 1));
}
}
}
0
}
}

#[test]
fn test() {
let graph = vec_vec_i32![[1, 2, 3], [0], [0], [0]];
let res = 4;
assert_eq!(Solution::shortest_path_length(graph), res);
let graph = vec_vec_i32![[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]];
let res = 4;
assert_eq!(Solution::shortest_path_length(graph), res);
}
``````