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 ith node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [uj, vj, timej] indicates that there is an undirected edge between the nodes uj and vj, and it takes timej seconds to travel between the two nodes. Finally, you are given an integer 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.

&nbsp;
Example 1:

Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
Output: 75
Explanation:
One possible path is 0 -&gt; 1 -&gt; 0 -&gt; 3 -&gt; 0. The total time taken is 10 + 10 + 10 + 10 = 40 &lt;= 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 = 30
Output: 25
Explanation:
One possible path is 0 -&gt; 3 -&gt; 0. The total time taken is 10 + 10 = 20 &lt;= 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 = 50
Output: 7
Explanation:
One possible path is 0 -&gt; 1 -&gt; 3 -&gt; 1 -&gt; 0. The total time taken is 10 + 13 + 13 + 10 = 46 &lt;= 50.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.


&nbsp;
Constraints:


	n == values.length
	1 &lt;= n &lt;= 1000
	0 &lt;= values[i] &lt;= 108
	0 &lt;= edges.length &lt;= 2000
	edges[j].length == 3 
	0 &lt;= uj &lt; vj &lt;= n - 1
	10 &lt;= timej, maxTime &lt;= 100
	All the pairs [uj, vj] are unique.
	There are at most four edges connected to each node.
	The graph may not be connected.


class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        graph = defaultdict(list)
		# build graph
        for edge in edges:
            graph[edge[0]].append((edge[1], edge[2]))
            graph[edge[1]].append((edge[0], edge[2]))
        
        q = deque()
        q.append((0, 0, values[0], set([0])))
        cache = {}
        maxPoint = 0
		
        while q:
            currV, currTime, currPoints, currSet = q.popleft()
            if currV in cache:
				# if vertex has been visited, and if the previousTime is 
				# less or equal to current time but current points is lower?
				# then this path can't give us better quality so stop proceeding.
                prevTime, prevPoints = cache[currV]
                if prevTime <= currTime and prevPoints > currPoints:
                    continue
            cache[currV] = (currTime, currPoints)
			# can't go over the maxTime limit
            if currTime > maxTime:
                continue
			# collect maxPoint only if current vertex is 0
            if currV == 0:
                maxPoint = max(maxPoint, currPoints)
            for neigh, neighTime in graph[currV]:
                newSet = currSet.copy()
				# collects quality only if not collected before
                if neigh not in currSet:
                    newSet.add(neigh)
                    newPoint = currPoints + values[neigh]
                else:
                    newPoint = currPoints
                q.append((neigh, currTime + neighTime, newPoint, newSet))
        return maxPoint
class Solution {
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < n; ++i) adj[i] = new LinkedList();
        for (int[] e : edges) {
            int i = e[0], j = e[1], t = e[2];
            adj[i].add(new int[]{j, t});
            adj[j].add(new int[]{i, t});
        }
        int[] res = new int[1];
        int[] seen = new int[n];
        seen[0]++;
        dfs(adj, 0, values, maxTime, seen, res, values[0]);
        return res[0];
    }
    private void dfs(List<int[]>[] adj, int src, int[] values, int maxTime, int[] seen, int[] res, int sum) {
        if (0 == src) {
            res[0] = Math.max(res[0], sum);
        }
        if (0 > maxTime) return;
        for (int[] data : adj[src]) {
            int dst = data[0], t = data[1];
            if (0 > maxTime - t) continue;
            seen[dst]++;
            dfs(adj, dst, values, maxTime - t, seen, res, sum + (1 == seen[dst] ? values[dst] : 0));
            seen[dst]--;
        }
    }
}
class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        int res = values[0];
        vector<vector<pair<int,int>>> graph(n);
        for(int i=0;i<edges.size();i++)
        {
            graph[edges[i][0]].push_back({edges[i][1], edges[i][2]});
            graph[edges[i][1]].push_back({edges[i][0], edges[i][2]});
        }
        
        vector<int> visited(n, 0);
        dfs(graph, values, visited, res, 0, 0, 0, maxTime);
        return res;
    }
    
    void dfs(vector<vector<pair<int,int>>>& graph, vector<int>& values, vector<int>& visited, int& res, int node, int score, int time, int& maxTime)
    {
        if(time > maxTime)
            return;
        
        if(visited[node] == 0)
            score += values[node];
        
 &nbsp; &nbsp; &nbsp; &nbsp;visited[node]++;
		
 &nbsp; &nbsp; &nbsp;
 &nbsp; &nbsp; &nbsp; &nbsp;if(node == 0)
            res = max(res, score);
        
        for(auto it : graph[node])
        {
            int neigh = it.first;
            int newTime = time + it.second;
            dfs(graph, values, visited, res, neigh, score, newTime, maxTime);
        }
        
        visited[node]--;
    }
};
var maximalPathQuality = function(values, edges, maxTime) {
    const adjacencyList = values.map(() => []);
    for (const [node1, node2, time] of edges) {
        adjacencyList[node1].push([node2, time]);
        adjacencyList[node2].push([node1, time]);
    }

    const dfs = (node, quality, time, seen) => {
        // if we returned back to the 0 node, then we log it as a valid value
        let best = node === 0 ? quality : 0;

        // try to visit all the neighboring nodes within the maxTime
        // given while recording the max
        for (const [neighbor, routeTime] of adjacencyList[node]) {
            const totalTime = time + routeTime;
            if (totalTime > maxTime) continue;
            if (seen.has(neighbor)) {
                best = Math.max(best,
                                dfs(neighbor, quality, totalTime, seen));
            } else {
                seen.add(neighbor);
                best = Math.max(best,
                                dfs(neighbor, quality + values[neighbor], totalTime, seen));
                seen.delete(neighbor);
            }
        }
        return best;
    }
    return dfs(0, values[0], 0, new Set([0]));
};
Maximum Path Quality of a Graph