Maximum Path Quality of a Graph

// Accepted solution for LeetCode #2065: Maximum Path Quality of a Graph
class Solution {
    private List<int[]>[] g;
    private boolean[] vis;
    private int[] values;
    private int maxTime;
    private int ans;

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1], t = e[2];
            g[u].add(new int[] {v, t});
            g[v].add(new int[] {u, t});
        }
        vis = new boolean[n];
        vis[0] = true;
        this.values = values;
        this.maxTime = maxTime;
        dfs(0, 0, values[0]);
        return ans;
    }

    private void dfs(int u, int cost, int value) {
        if (u == 0) {
            ans = Math.max(ans, value);
        }
        for (var e : g[u]) {
            int v = e[0], t = e[1];
            if (cost + t <= maxTime) {
                if (vis[v]) {
                    dfs(v, cost + t, value);
                } else {
                    vis[v] = true;
                    dfs(v, cost + t, value + values[v]);
                    vis[v] = false;
                }
            }
        }
    }
}

// Accepted solution for LeetCode #2065: Maximum Path Quality of a Graph
func maximalPathQuality(values []int, edges [][]int, maxTime int) (ans int) {
	n := len(values)
	g := make([][][2]int, n)
	for _, e := range edges {
		u, v, t := e[0], e[1], e[2]
		g[u] = append(g[u], [2]int{v, t})
		g[v] = append(g[v], [2]int{u, t})
	}
	vis := make([]bool, n)
	vis[0] = true
	var dfs func(u, cost, value int)
	dfs = func(u, cost, value int) {
		if u == 0 {
			ans = max(ans, value)
		}
		for _, e := range g[u] {
			v, t := e[0], e[1]
			if cost+t <= maxTime {
				if vis[v] {
					dfs(v, cost+t, value)
				} else {
					vis[v] = true
					dfs(v, cost+t, value+values[v])
					vis[v] = false
				}
			}
		}
	}
	dfs(0, 0, values[0])
	return
}

# Accepted solution for LeetCode #2065: Maximum Path Quality of a Graph
class Solution:
    def maximalPathQuality(
        self, values: List[int], edges: List[List[int]], maxTime: int
    ) -> int:
        def dfs(u: int, cost: int, value: int):
            if u == 0:
                nonlocal ans
                ans = max(ans, value)
            for v, t in g[u]:
                if cost + t <= maxTime:
                    if vis[v]:
                        dfs(v, cost + t, value)
                    else:
                        vis[v] = True
                        dfs(v, cost + t, value + values[v])
                        vis[v] = False

        n = len(values)
        g = [[] for _ in range(n)]
        for u, v, t in edges:
            g[u].append((v, t))
            g[v].append((u, t))
        vis = [False] * n
        vis[0] = True
        ans = 0
        dfs(0, 0, values[0])
        return ans

// Accepted solution for LeetCode #2065: Maximum Path Quality of a Graph
/**
 * [2065] Maximum Path Quality of a Graph
 *
 * 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 i^th 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.
 *  
 * Example 1:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex1drawio.png" style="width: 269px; height: 170px;" />
 * Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
 * Output: 75
 * Explanation:
 * One possible path is 0 -> 1 -> 0 -> 3 -> 0. The total time taken is 10 + 10 + 10 + 10 = 40 <= 49.
 * The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.
 *
 * Example 2:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex2drawio.png" style="width: 269px; height: 170px;" />
 * Input: values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
 * Output: 25
 * Explanation:
 * One possible path is 0 -> 3 -> 0. The total time taken is 10 + 10 = 20 <= 30.
 * The nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.
 *
 * Example 3:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex31drawio.png" style="width: 236px; height: 170px;" />
 * Input: values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
 * Output: 7
 * Explanation:
 * One possible path is 0 -> 1 -> 3 -> 1 -> 0. The total time taken is 10 + 13 + 13 + 10 = 46 <= 50.
 * The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.
 *
 *  
 * Constraints:
 *
 * 	n == values.length
 * 	1 <= n <= 1000
 * 	0 <= values[i] <= 10^8
 * 	0 <= edges.length <= 2000
 * 	edges[j].length == 3
 * 	0 <= uj < vj <= n - 1
 * 	10 <= timej, maxTime <= 100
 * 	All the pairs [uj, vj] are unique.
 * 	There are at most four edges connected to each node.
 * 	The graph may not be connected.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-path-quality-of-a-graph/
// discuss: https://leetcode.com/problems/maximum-path-quality-of-a-graph/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn maximal_path_quality(values: Vec<i32>, edges: Vec<Vec<i32>>, max_time: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2065_example_1() {
        let values = vec![0, 32, 10, 43];
        let edges = vec![vec![0, 1, 10], vec![1, 2, 15], vec![0, 3, 10]];
        let max_time = 49;

        let result = 75;

        assert_eq!(
            Solution::maximal_path_quality(values, edges, max_time),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_2065_example_2() {
        let values = vec![5, 10, 15, 20];
        let edges = vec![vec![0, 1, 10], vec![1, 2, 10], vec![0, 3, 10]];
        let max_time = 30;

        let result = 25;

        assert_eq!(
            Solution::maximal_path_quality(values, edges, max_time),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_2065_example_3() {
        let values = vec![1, 2, 3, 4];
        let edges = vec![
            vec![0, 1, 10],
            vec![1, 2, 11],
            vec![2, 3, 12],
            vec![1, 3, 13],
        ];
        let max_time = 50;

        let result = 7;

        assert_eq!(
            Solution::maximal_path_quality(values, edges, max_time),
            result
        );
    }
}

// Accepted solution for LeetCode #2065: Maximum Path Quality of a Graph
function maximalPathQuality(values: number[], edges: number[][], maxTime: number): number {
    const n = values.length;
    const g: [number, number][][] = Array.from({ length: n }, () => []);
    for (const [u, v, t] of edges) {
        g[u].push([v, t]);
        g[v].push([u, t]);
    }
    const vis: boolean[] = Array(n).fill(false);
    vis[0] = true;
    let ans = 0;
    const dfs = (u: number, cost: number, value: number) => {
        if (u === 0) {
            ans = Math.max(ans, value);
        }
        for (const [v, t] of g[u]) {
            if (cost + t <= maxTime) {
                if (vis[v]) {
                    dfs(v, cost + t, value);
                } else {
                    vis[v] = true;
                    dfs(v, cost + t, value + values[v]);
                    vis[v] = false;
                }
            }
        }
    };
    dfs(0, 0, values[0]);
    return ans;
}