Maximum Score of a Node Sequence LeetCode solution in Rust

1
use std::cmp::Reverse;
2
use std::collections::BinaryHeap;
3

4
pub fn to_graph(edges: &Vec<(usize, usize)>, scores: &Vec<u32>) -> Vec<Vec<usize>> {
5
  const HEAP_THRESHOLD: usize = 3;
6

7
  let n = scores.len();
8

9
  let mut ret = vec![BinaryHeap::new(); n];
10

11
  for &(v0, v1) in edges {
12
    let e0 = scores[v0];
13
    let e1 = scores[v1];
14

15
    ret[v0].push(Reverse((e1, v1)));
16
    ret[v1].push(Reverse((e0, v0)));
17

18
    if ret[v0].len() > HEAP_THRESHOLD {
19
      ret[v0].pop();
20
    }
21
    if ret[v1].len() > HEAP_THRESHOLD {
22
      ret[v1].pop();
23
    }
24
  }
25

26
  ret
27
    .into_iter()
28
    .map(|heap| heap.into_iter().map(|e| e.0 .1).collect::<Vec<_>>())
29
    .collect::<Vec<_>>()
30
}
31

32
impl Solution {
33
  pub fn maximum_score(scores: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
34
    let scores = scores.into_iter().map(|e| e as u32).collect::<Vec<_>>();
35
    let edges = edges
36
      .into_iter()
37
      .filter(|v| v.len() == 2)
38
      .map(|v| v.into_iter().map(|e| e as usize).collect::<Vec<_>>())
39
      .map(|v| (v[0], v[1]))
40
      .filter(|(v0, v1)| v0 != v1)
41
      .collect::<Vec<_>>();
42
    let graph = to_graph(&edges, &scores);
43

44
    let mut ret = None;
45
    for (v0, v1) in edges {
46
      let mut _ret = None;
47
      for v0_next in graph[v0].clone() {
48
        if v0_next == v1 {
49
          continue;
50
        }
51
        let e0_next = scores[v0_next];
52
        for v1_next in graph[v1].clone() {
53
          if v1_next == v0 {
54
            continue;
55
          }
56
          if v0_next == v1_next {
57
            continue;
58
          }
59
          let e1_next = scores[v1_next];
60
          _ret = Some(_ret.unwrap_or(u32::MIN).max(e0_next + e1_next));
61
        }
62
      }
63
      let mut _ret = if let Some(inner) = _ret {
64
        inner
65
      } else {
66
        continue;
67
      };
68
      _ret += scores[v0];
69
      _ret += scores[v1];
70

71
      ret = Some(ret.unwrap_or(u32::MIN).max(_ret));
72
    }
73

74
    ret.map(|e| e as i32).unwrap_or(-1)
75
  }
76
}