Maximum Value Collected on a Time-Bounded Tour
An inspector tours a network of sites, each worth some value, starting and ending at site 0 within a time budget. Each site's value counts once no matter how often visited. Maximize the value collected.
Problem
Given an undirected graph with node values[] and edges where edge [u, v, t] takes t time to traverse, plus an integer maxTime, find a walk that starts and ends at node 0 with total traversal time at most maxTime. The quality is the sum of values of distinct nodes visited. Return the maximum quality.
Input
An array values, an array edges of [u, v, time], and an integer maxTime.
Output
An integer: the maximum quality of a valid round-trip walk.
Constraints
- 1 <= values.length <= 1000
- 0 <= edges.length <= 2000; each node has at most 4 incident edges
- 10 <= timeCost per edge, maxTime <= 100 (so few edges fit in budget).
Examples
Example 1
Input
values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
Output
75
0->1->0->3->0 collects 0+32+43 = 75 within 49 time.
Example 2
Input
values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
Output
25
0->3->0->... best collects 5 + 20 = 25.