282. Maximum Total Beauty Within Travel Time

Maximum Total Beauty Within Travel Time

You are given locations connected by undirected roads. Each location has a beauty value, and each road has a travel time. Starting at location 0, find the maximum total beauty that can be collected within maxTime while returning to location 0.

Route Rules

The route starts and ends at location 0.
A location's beauty is collected the first time it is visited.
Visiting the same location again does not add its beauty again.
Roads may be traversed multiple times, and their travel time is counted every time.
The total travel time must not exceed maxTime.
Remaining at location 0 without using any road is a valid route.

Input Representation

beautyValues.get(i) is the beauty value of location i.
Each string in connections has the format "u,v", representing an undirected road between locations u and v.
travelTimes.get(i) is the travel time of the road represented by connections.get(i).

Method Signature

int findMaximumBeauty( List<Integer> beautyValues, List<Integer> travelTimes, List<String> connections, int maxTime )

Parameters

beautyValues: the beauty value of every location.
travelTimes: the travel time of every road.
connections: the pairs of locations connected by roads.
maxTime: the maximum permitted travel time.

Returns

Return the maximum total beauty obtainable by a valid route.

Constraints

1 ≤ beautyValues.size() ≤ 1,000
0 ≤ beautyValues.get(i) ≤ 100
0 ≤ connections.size() ≤ 2,000
travelTimes.size() = connections.size()
Every connection contains exactly two different valid location indexes.
10 ≤ travelTimes.get(i) ≤ 100
1 ≤ maxTime ≤ 100
Each location is connected to at most four roads.

Examples

Example 1

 findMaximumBeauty( beautyValues = List.of(7, 15, 9, 20), travelTimes = List.of(10, 10, 12), connections = List.of("0,1", "1,2", "0,3"), maxTime = 32 )

Output: 27

The route 0 → 3 → 0 takes 24 time and collects beauty 7 + 20 = 27.

Example 2

 findMaximumBeauty( beautyValues = List.of(4, 6, 13, 8), travelTimes = List.of(10, 10, 10), connections = List.of("0,1", "1,2", "1,3"), maxTime = 60 )

Output: 31

The route 0 → 1 → 2 → 1 → 3 → 1 → 0 takes exactly 60 time and collects every location's beauty once.

Example 3

 findMaximumBeauty( beautyValues = List.of(11, 50), travelTimes = List.of(20), connections = List.of("0,1"), maxTime = 30 )

Output: 11

Visiting location 1 and returning would require 40 time, so the best valid route remains at location 0.