Maximum cost of trip with k highways

Dynamic Programming Bit Manipulation Graph Theory Bitmask

51.1% acceptance

Mar 31, 2026

A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli. You are also given an integer k. You are going on a trip that crosses exactly k highways. You may start at any city, but you may only visit each city at most once during your trip. Return the maximum cost of your trip. If there is no trip that meets the requirements, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_cost(n: i32, highways: Vec<Vec<i32>>, k: i32) -> i32 {
    let n = n as usize;
    let k = k as usize;
    if k >= n { return -1; }
    let mut adj = vec![vec![]; n];
    for h in &highways {
      let (u, v, c) = (h[0] as usize, h[1] as usize, h[2]);
      adj[u].push((v, c));
      adj[v].push((u, c));
    }
    let total_states = 1 << n;
    let mut dp = vec![vec![-1i32; n]; total_states];
    for i in 0..n {
      dp[1 << i][i] = 0;
    }
    let mut ans = -1;
    for mask in 1..total_states {
      for u in 0..n {
        if dp[mask][u] < 0 || mask & (1 << u) == 0 { continue; }
        if (mask as u32).count_ones() as usize == k + 1 {
          ans = ans.max(dp[mask][u]);
        }
        for &(v, c) in &adj[u] {
          if mask & (1 << v) != 0 { continue; }
          let new_mask = mask | (1 << v);
          dp[new_mask][v] = dp[new_mask][v].max(dp[mask][u] + c);
        }
      }
    }
    ans
  }
}