Minimum Cost to Connect Two Groups of Points LeetCode solution in Rust

1
impl Solution {
2
  pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
3
    let (s1, s2) = (cost.len(), cost[0].len());
4

5
    let min = (0..s2)
6
      .map(|j| (0..s1).fold(i32::MAX, |acc, i| acc.min(cost[i][j])))
7
      .collect::<Vec<_>>();
8

9
    let mut dp = (0..2_usize.pow(s2 as u32))
10
      .map(|m| {
11
        let mut cost = 0;
12
        for b in 0..s2 {
13
          if (m >> b) & 1 == 1 {
14
            continue;
15
          };
16
          cost += min[b];
17
        }
18
        cost
19
      })
20
      .collect::<Vec<_>>();
21

22
    for i in (0..s1) {
23
      let mut new = vec![i32::MAX; 2_usize.pow(s2 as u32)];
24
      for m in (0..2_usize.pow(s2 as u32)) {
25
        for b in (0..s2) {
26
          new[m] = new[m].min(cost[i][b] + dp[m | (1 << b)]);
27
        }
28
      }
29
      dp = new;
30
    }
31
    dp[0]
32
  }
33
}