847. Shortest Path Visiting All Nodes Hard

1/**
2 * [847] Shortest Path Visiting All Nodes
3 *
4 * You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest1-graph.jpg" style="width: 222px; height: 183px;" />
9 * Input: graph = [[1,2,3],[0],[0],[0]]
10 * Output: 4
11 * Explanation: One possible path is [1,0,2,0,3]
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/12/shortest2-graph.jpg" style="width: 382px; height: 222px;" />
15 * Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
16 * Output: 4
17 * Explanation: One possible path is [0,1,4,2,3]
18 * 
19 *  
20 * Constraints:
21 * 
22 * 	n == graph.length
23 * 	1 <= n <= 12
24 * 	0 <= graph[i].length < n
25 * 	graph[i] does not contain i.
26 * 	If graph[a] contains b, then graph[b] contains a.
27 * 	The input graph is always connected.
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/shortest-path-visiting-all-nodes/
33// discuss: https://leetcode.com/problems/shortest-path-visiting-all-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    pub fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
39        0
40    }
41}
42
43// submission codes end
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test_847() {
51    }
52}
53