Maximum weighted k edge path

Hash Table Dynamic Programming Graph Theory

19.9% acceptance

Feb 25, 2026

You are given a DAG with n nodes and edges[i]=[ui,vi,wi] (directed edge ui->vi with weight wi). Find the maximum sum of edge weights for a path with exactly k edges and total sum strictly less than t. Return -1 if no such path exists.

Solution

Rust

Time O(n * m)

Space O(n * k * t/64)

LeetCode

solution.rs

impl Solution {
  pub fn max_weight(n: i32, edges: Vec<Vec<i32>>, k: i32, t: i32) -> i32 {
    let n = n as usize;
    let k = k as usize;
    let t = t as usize;
    
    // dp[v][e] = bitmask of achievable sums < t at node v with exactly e directed edges.
    // bit s set iff sum s is reachable at node v using exactly e edges.
    // O(n * k * t/64) space ~ 7MB – acceptable.
    let t_words = (t + 63) / 64;
    let mut dp: Vec<Vec<Vec<u64>>> = vec![vec![vec![0u64; t_words]; k + 1]; n];

    // Base case: 0 edges, sum 0 reachable at every node (path can start anywhere).
    if t > 0 {
      for v in 0..n {
        dp[v][0][0] = 1; // bit 0 set
      }
    }

    // Process layered: for each number of edges from 1 to k.
    // For each directed edge (u->v, w): dp[v][step] |= left_shift(dp[u][step-1], w).
    // No clone needed: dp[v][step] only depends on dp[u][step-1], different layers.
    for step in 1..=k {
      for e in &edges {
        let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as usize);
        let shifted = shift_bits(&dp[u][step - 1], w, t);
        for i in 0..t_words {
          dp[v][step][i] |= shifted[i];
        }
      }
    }
    
    // Find maximum sum < t achievable with exactly k edges at any node
    // Find maximum sum < t achievable with exactly k edges at any node.
    let mut ans = -1i32;
    for v in 0..n {
      for s in (0..t).rev() {
        if get_bit(&dp[v][k], s) {
          if s as i32 > ans {
            ans = s as i32;
          }
          break;
        }
      }
    }
    ans
  }
}

fn get_bit(bits: &[u64], pos: usize) -> bool {
  bits[pos / 64] & (1u64 << (pos % 64)) != 0
}

/// Left-shift a bitset by `shift` positions, retaining only bits 0..limit-1.
fn shift_bits(bits: &[u64], shift: usize, limit: usize) -> Vec<u64> {
  let t_words = (limit + 63) / 64;
  let mut result = vec![0u64; t_words];
  let word_shift = shift / 64;
  let bit_shift = shift % 64;

  for i in 0..t_words {
    // High portion of result[i]: bits from bits[i - word_shift] shifted left.
    if i >= word_shift {
      let src = i - word_shift;
      if src < bits.len() {
        result[i] |= bits[src] << bit_shift;
      }
    }
    // Low portion of result[i]: carry from bits[i - word_shift - 1] shifted right.
    // These are bits that overflow the previous word's left-shift.
    if bit_shift > 0 && i >= word_shift + 1 {
      let src = i - word_shift - 1;
      if src < bits.len() {
        result[i] |= bits[src] >> (64 - bit_shift);
      }
    }
  }

  // Mask out bits >= limit.
  if limit > 0 {
    let last_word = (limit - 1) / 64;
    let last_bit = limit % 64;
    if last_bit != 0 && last_word < t_words {
      result[last_word] &= (1u64 << last_bit) - 1;
    }
  }
  result
}