Maximum Path Quality of a Graph

Challenge Points: 30

Level: Hard

You are given an undirected graph of n nodes, numbered from 0 to n−1. Each node has a value defined in the array values, where values[i] is the value for node i.
You are also provided a list of edges, where each edge is described as [u, v, t] meaning that traveling between node u and node v requires t seconds.
You are also given an integer maxTime.

A valid route must:

start at node 0,
end at node 0,
and the total travel time must not exceed maxTime.

You may revisit nodes, but the quality of a route is the sum of values of distinct nodes visited at least once.

Your task is to compute the maximum achievable path quality over all valid routes.

Note: Each node is connected to at most four others.

Example 1:

Input: values = [3, 8, 12, 5], edges = [[0,1,5],[1,2,20],[2,3,15],[0,3,10]], maxTime = 40

Output: 23

Explanation:

A valid route is: 0 → 1 → 0 → 3 → 0 Time used = 5 + 5 + 10 + 10 = 30 ≤ 40 Unique visited nodes = {0,1,3} → quality = 3 + 8 + 5 = 23

Example 2:

Input: values = [7, 4, 9], edges = [[0,1,12],[1,2,12],[0,2,30]], maxTime = 25

Output: 16

Explanation:

Route: 0 → 1 → 0 Time = 12 + 12 = 24 ≤ 25 Unique visited = {0,1} → 7 + 4 = 11 But route 0 → 1 → 2 → 1 → 0 uses time 12 + 12 + 12 + 12 = 48 (too large) Best is 16 using path that visits nodes {0,1,2} within time limit.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result