##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2065.html

# 2065. Maximum Path Quality of a Graph (Hard)

There is an **undirected** graph with `n`

nodes numbered from `0`

to `n - 1`

(**inclusive**). You are given a **0-indexed** integer array `values`

where `values[i]`

is the **value **of the `i`

node. You are also given a ^{th}**0-indexed** 2D integer array `edges`

, where each `edges[j] = [u`

indicates that there is an undirected edge between the nodes _{j}, v_{j}, time_{j}]`u`

and _{j}`v`

,_{j}_{ }and it takes `time`

seconds to travel between the two nodes. Finally, you are given an integer _{j}`maxTime`

.

A **valid** **path** in the graph is any path that starts at node `0`

, ends at node `0`

, and takes **at most** `maxTime`

seconds to complete. You may visit the same node multiple times. The **quality** of a valid path is the **sum** of the values of the **unique nodes** visited in the path (each node's value is added **at most once** to the sum).

Return *the maximum quality of a valid path*.

**Note:** There are **at most four** edges connected to each node.

**Example 1:**

Input:values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49Output:75Explanation:One possible path is 0 -> 1 -> 0 -> 3 -> 0. The total time taken is 10 + 10 + 10 + 10 = 40 <= 49. The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.

**Example 2:**

Input:values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30Output:25Explanation:One possible path is 0 -> 3 -> 0. The total time taken is 10 + 10 = 20 <= 30. The nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.

**Example 3:**

Input:values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50Output:7Explanation:One possible path is 0 -> 1 -> 3 -> 1 -> 0. The total time taken is 10 + 13 + 13 + 10 = 46 <= 50. The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.

**Example 4:**

Input:values = [0,1,2], edges = [[1,2,10]], maxTime = 10Output:0Explanation:The only path is 0. The total time taken is 0. The only node visited is 0, giving a maximal path quality of 0.

**Constraints:**

`n == values.length`

`1 <= n <= 1000`

`0 <= values[i] <= 10`

^{8}`0 <= edges.length <= 2000`

`edges[j].length == 3`

`0 <= u`

_{j }< v_{j}<= n - 1`10 <= time`

_{j}, maxTime <= 100- All the pairs
`[u`

are_{j}, v_{j}]**unique**. - There are
**at most four**edges connected to each node. - The graph may not be connected.

**Similar Questions**:

## Solution 1. DFS

Since `10 <= timej, maxTime <= 100`

, the path at most have `10`

edges. Since each node at most has `4`

edges, the maximum number of possible paths is `4^10 ~= 1e6`

, so a brute force DFS should work.

```
// OJ: https://leetcode.com/problems/maximum-path-quality-of-a-graph/
// Time: O(4^10)
// Space: O(V + E)
class Solution {
public:
int maximalPathQuality(vector<int>& V, vector<vector<int>>& E, int maxTime) {
int N = V.size();
vector<vector<pair<int, int>>> G(N); // build graph
for (auto &e : E) {
int u = e[0], v = e[1], c = e[2];
G[u].emplace_back(v, c);
G[v].emplace_back(u, c);
}
vector<int> cnt(N); // `cnt[u]` is the number of times we've visted node `u` in the current path
int ans = 0;
function<void(int, int, int)> dfs = [&](int u, int val, int time) {
if (cnt[u] == 0) val += V[u];
cnt[u]++;
if (u == 0) ans = max(ans, val); // Only update answer if the current node is `0`.
for (auto &[v, c] : G[u]) {
if (time + c > maxTime) continue; // if the current time + the edge time is greater than maxTime, skip
dfs(v, val, time + c);
}
cnt[u]--;
};
dfs(0, 0, 0);
return ans;
}
};
```

Or we can optionally add Dijkstra to backtrack earlier.

```
// OJ: https://leetcode.com/problems/maximum-path-quality-of-a-graph/
// Time: O(ElogE + 4^10)
// Space: O(V + E)
class Solution {
typedef array<int, 2> T;
public:
int maximalPathQuality(vector<int>& V, vector<vector<int>>& E, int maxTime) {
int N = V.size();
vector<vector<array<int, 2>>> G(N); // build graph
for (auto &e : E) {
int u = e[0], v = e[1], c = e[2];
G[u].push_back({v, c});
G[v].push_back({u, c});
}
priority_queue<T, vector<T>, greater<T>> pq; // use Dijkstra to find the shortest distance from node 0 to all other nodes.
vector<int> dist(N, INT_MAX);
dist[0] = 0;
pq.push({0, 0});
while (pq.size()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto &[v, c] : G[u]) {
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
pq.push({dist[v], v});
}
}
}
vector<int> cnt(N); // `cnt[u]` is the number of times we've visted node `u` in the current path
int ans = 0;
function<void(int, int, int)> dfs = [&](int u, int val, int time) {
if (cnt[u] == 0) val += V[u];
cnt[u]++;
if (u == 0) ans = max(ans, val); // Only update answer if the current node is `0`.
for (auto &[v, c] : G[u]) {
if (time + c + dist[v] > maxTime) continue; // if the current time + the edge time + dist[u] is greater than maxTime, skip
dfs(v, val, time + c);
}
cnt[u]--;
};
dfs(0, 0, 0);
return ans;
}
};
```