Practice/Amazon/Leetcode 2065. Maximum Path Quality of a Graph

Leetcode 2065. Maximum Path Quality of a Graph

CodingOptional

Problem

You are given an undirected weighted graph where each node has an associated value. Your task is to find the maximum sum of unique node values you can collect on any valid journey that:

• Starts at node 0
• Ends at node 0
• Takes at most maxTime time units

Each edge has a travel time cost, and while you may visit nodes multiple times during your journey, each node's value contributes to your total sum at most once (only counted on the first visit).

The graph is represented by:

• values: an array where values[i] is the value of node i
• edges: a list of undirected edges where each edge is [u, v, time] indicating nodes u and v are connected with travel time time
• maxTime: the maximum time budget for your entire journey

Requirements

1. Return the maximum sum of unique node values achievable
2. The path must start and end at node 0
3. Total travel time must not exceed maxTime
4. Each node's value is counted at most once, regardless of how many times you visit it
5. You may revisit nodes and traverse edges multiple times

Constraints

• 1 ≤ n ≤ 1000 (number of nodes)
• 0 ≤ edges.length ≤ 2000
• 0 ≤ values[i] ≤ 108
• 0 ≤ u, v < n
• 1 ≤ time ≤ 10
• 1 ≤ maxTime ≤ 100
• The graph is connected
• Each node has at most 4 neighbors

Examples

Example 1:

` Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49 Output: 75 Explanation: One optimal path is 0 → 3 → 0 → 1 → 0

• Visit node 0 (value 0)
• Travel to node 3 (10 time units, value 43)
• Return to node 0 (10 time units, already counted)
• Travel to node 1 (10 time units, value 32)
• Return to node 0 (10 time units, already counted) Total time: 40 units, Total value: 0 + 43 + 32 = 75 `

Example 2:

Input: values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30 Output: 25 Explanation: The path 0 → 3 → 0 takes 20 time units and collects values 5 + 20 = 25. We cannot reach node 2 and return to node 0 within the time budget.