Best Unique-Node Value on a Timed Return Walk
Company: Nutanix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
An undirected graph has vertices numbered from `0` through `n - 1`, with value `values[i]` at vertex `i`. Each edge `[u, v, travelTime]` takes `travelTime` seconds to traverse in either direction. Start at vertex `0` and return to it within `maxTime` seconds. The value of a walk is the sum of the values of the distinct vertices it visits: revisiting a vertex does not score it again. Return the greatest value of a valid walk. You may stay at vertex `0` without traversing an edge. Each vertex has at most four incident edges.
```cpp
class Solution {
public:
int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime);
};
```
### Examples
**Example 1:**
```text
values = [3,8], edges = [[0,1,10]], maxTime = 20
Output: 11
Explanation: The round trip 0->1->0 visits both nodes within the budget.
```
**Example 2:**
```text
values = [6,100], edges = [[0,1,10]], maxTime = 10
Output: 6
Explanation: Visiting node 1 leaves no time to return, so staying at 0 is best.
```
### Constraints
- `1 <= values.length <= 1000`; `0 <= values[i] <= 10^8`.
- `0 <= edges.length <= 2000`; edges are unique pairs with `0 <= u < v < n`.
- Edge times and maxTime lie in `[10,100]`.
- Maximum degree is four; the graph may be disconnected.
### Clarifying Questions
Only walks ending back at zero contribute an answer. Visiting a node repeatedly does not add its value again.
```hint Inspect the structure
How does the minimum edge duration bound the depth of exhaustive walk exploration?
```
### Reasoning checkpoints
- Enforce the time limit on a walk that finishes back at its starting vertex.
- Score each distinct visited vertex once while allowing repeated visits and traversals.
- Justify that the search or optimization covers every feasible return walk under the supplied bounds.
### Optional extensions
What additional information could rule out a partial walk that cannot return to the start in time?
Overview: Best Unique-Node Value on a Timed Return Walk. An undirected graph has node values and edges [u,v,travelTime]. Start at 0, return to 0 within maxTime, and maximize the sum of values of distinct visited nodes. Repeated visits are allowed but score a node only once. A zero-edge walk is allowed. Each node has at most four incident edges.
