DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

2 1

Maximum Path Quality of a Graph

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.

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 -> 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 = 30
Output: 25
Explanation:
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 = 50
Output: 7
Explanation:
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.

Constraints:

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

SOLUTION:

from collections import defaultdict

class Solution:
    def getPath(self, node, graph, visited, time, values, maxTime):
        if node == 0:
            currQuality = sum([values[i] for i in visited])
            if currQuality >= self.maxQuality:
                self.maxQuality = currQuality
        for j, t in graph[node]:
            if time + t <= maxTime:
                self.getPath(j, graph, visited.union({j}), time + t, values, maxTime)

    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        self.maxQuality = float('-inf')
        graph = defaultdict(list)
        for a, b, t in edges:
            graph[a].append((b, t))
            graph[b].append((a, t))
        self.getPath(0, graph, {0}, 0, values, maxTime)
        return self.maxQuality
Enter fullscreen mode Exit fullscreen mode

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️