2959. Number of Possible Sets of Closing Branches Hard

1/**
2 * [2959] Number of Possible Sets of Closing Branches
3 *
4 * There is a company with n branches across the country, some of which are connected by roads. Initially, all branches are reachable from each other by traveling some roads.
5 * The company has realized that they are spending an excessive amount of time traveling between their branches. As a result, they have decided to close down some of these branches (possibly none). However, they want to ensure that the remaining branches have a distance of at most maxDistance from each other.
6 * The distance between two branches is the minimum total traveled length needed to reach one branch from another.
7 * You are given integers n, maxDistance, and a 0-indexed 2D array roads, where roads[i] = [ui, vi, wi] represents the undirected road between branches ui and vi with length wi.
8 * Return the number of possible sets of closing branches, so that any branch has a distance of at most maxDistance from any other.
9 * Note that, after closing a branch, the company will no longer have access to any roads connected to it.
10 * Note that, multiple roads are allowed.
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2023/11/08/example11.png" style="width: 221px; height: 191px;" />
14 * Input: n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
15 * Output: 5
16 * Explanation: The possible sets of closing branches are:
17 * - The set [2], after closing, active branches are [0,1] and they are reachable to each other within distance 2.
18 * - The set [0,1], after closing, the active branch is [2].
19 * - The set [1,2], after closing, the active branch is [0].
20 * - The set [0,2], after closing, the active branch is [1].
21 * - The set [0,1,2], after closing, there are no active branches.
22 * It can be proven, that there are only 5 possible sets of closing branches.
23 * 
24 * <strong class="example">Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2023/11/08/example22.png" style="width: 221px; height: 241px;" />
26 * Input: n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
27 * Output: 7
28 * Explanation: The possible sets of closing branches are:
29 * - The set [], after closing, active branches are [0,1,2] and they are reachable to each other within distance 4.
30 * - The set [0], after closing, active branches are [1,2] and they are reachable to each other within distance 2.
31 * - The set [1], after closing, active branches are [0,2] and they are reachable to each other within distance 2.
32 * - The set [0,1], after closing, the active branch is [2].
33 * - The set [1,2], after closing, the active branch is [0].
34 * - The set [0,2], after closing, the active branch is [1].
35 * - The set [0,1,2], after closing, there are no active branches.
36 * It can be proven, that there are only 7 possible sets of closing branches.
37 * 
38 * <strong class="example">Example 3:
39 * 
40 * Input: n = 1, maxDistance = 10, roads = []
41 * Output: 2
42 * Explanation: The possible sets of closing branches are:
43 * - The set [], after closing, the active branch is [0].
44 * - The set [0], after closing, there are no active branches.
45 * It can be proven, that there are only 2 possible sets of closing branches.
46 * 
47 *  
48 * Constraints:
49 * 
50 * 	1 <= n <= 10
51 * 	1 <= maxDistance <= 10^5
52 * 	0 <= roads.length <= 1000
53 * 	roads[i].length == 3
54 * 	0 <= ui, vi <= n - 1
55 * 	ui != vi
56 * 	1 <= wi <= 1000
57 * 	All branches are reachable from each other by traveling some roads.
58 * 
59 */
60pub struct Solution {}
61
62// problem: https://leetcode.com/problems/number-of-possible-sets-of-closing-branches/
63// discuss: https://leetcode.com/problems/number-of-possible-sets-of-closing-branches/discuss/?currentPage=1&orderBy=most_votes&query=
64
65// submission codes start here
66
67impl Solution {
68    pub fn number_of_sets(n: i32, max_distance: i32, roads: Vec<Vec<i32>>) -> i32 {
69        0
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_2959() {
81    }
82}
83