Maximum path quality of a graph

Array Backtracking Graph Theory

61.7% acceptance

Feb 25, 2026

722

There is an undirected graph with n nodes numbered from 0 to n - 1 (inclusive). You are given a 0-indexed integer array values where values[i] is the value of the ith node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [uj, vj, timej] indicates that there is an undirected edge between the nodes uj and vj, and it takes timej seconds to travel between the two nodes. Finally, you are given an integer maxTime. A valid path in the graph is any path that starts at node 0, ends at node 0, and takes at most maxTime seconds to complete. You may visit the same node multiple times. The quality of a valid path is the sum of the values of the unique nodes visited in the path (each node's value is added at most once to the sum). Return the maximum quality of a valid path. Note: There are at most four edges connected to each node.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximal_path_quality(values: Vec<i32>, edges: Vec<Vec<i32>>, max_time: i32) -> i32 {
    let n = values.len();
    let mut adj = vec![vec![]; n];
    for e in &edges {
      let (u, v, t) = (e[0] as usize, e[1] as usize, e[2]);
      adj[u].push((v, t));
      adj[v].push((u, t));
    }

    let mut ans = 0i32;
    let mut visit_count = vec![0i32; n];
    visit_count[0] = 1;

    fn dfs(
      u: usize,
      time_left: i32,
      quality: i32,
      visit_count: &mut Vec<i32>,
      values: &[i32],
      adj: &[Vec<(usize, i32)>],
      ans: &mut i32,
    ) {
      if u == 0 {
        *ans = (*ans).max(quality);
      }
      for &(v, t) in &adj[u] {
        if time_left >= t {
          let added = if visit_count[v] == 0 { values[v] } else { 0 };
          visit_count[v] += 1;
          dfs(v, time_left - t, quality + added, visit_count, values, adj, ans);
          visit_count[v] -= 1;
        }
      }
    }

    dfs(0, max_time, values[0], &mut visit_count, &values, &adj, &mut ans);
    ans
  }
}