Find the maximum total value of unique nodes visited on a path that starts and ends at node 0 within a time limit.
Problem
You are given an undirected weighted graph with nodes labeled from $0n-1$.
Each node has a value. You start at node 0 at time 0. You may travel along edges, and traversing an edge consumes the given amount of time. You may visit nodes and edges multiple times, but the total travel time must not exceed maxTime.
The quality of a path is the sum of the values of all distinct nodes visited at least once on that path.
Return the maximum possible path quality among all valid paths that start at node 0, end at node 0, and use at most maxTime time.
Notes
- Visiting the same node multiple times counts its value only once.
- A valid path may revisit nodes and edges.
- You only score nodes that appear at least once in the route.
Input Format
values: integer array wherevalues[i]is the value of nodeiedges: list of undirected edges, each represented as[u, v, time]maxTime: maximum total travel time allowed
Output Format
- Return the maximum achievable path quality for any valid route starting and ending at
0.
Constraints
- The graph is undirected
- Edge times are positive integers
- The route must start and end at node
0 - Total travel time must be
<= maxTime
Hints
- Since node values are only counted once, keep track of which nodes have already been collected.
- Explore all feasible routes with pruning when the remaining time cannot return to node
0. - A node may be visited multiple times, but revisiting it should not add value again.
Input Format
values[i]gives the score contribution of nodeiedges[j] = [u, v, time]describes an undirected edge betweenuandvmaxTimeis the travel budget
Output Format
- Return a single integer: the maximum path quality of any valid route that begins and ends at node
0withinmaxTime
Constraints
- Each edge is undirected and has positive travel time
Note: these bounds are representative for practice and not guaranteed to match the original platform statement exactly.
Example 1
Input
values = [0,32,10,43] edges = [[0,1,10],[1,2,15],[0,3,10]] maxTime = 49
Output
75
Explanation
One best route is 0 -> 1 -> 0 -> 3 -> 0, which visits nodes {0,1,3}. The total quality is 0 + 32 + 43 = 75.
Example 2
Input
values = [5,10,15] edges = [[0,1,10],[1,2,10],[0,2,20]] maxTime = 20
Output
20
Explanation
The route 0 -> 2 -> 0 is valid and collects nodes {0,2} for a total quality of 5 + 15 = 20. Going through node 1 would not improve the best return-to-start route within the time limit.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.