Problem statement

https://leetcode.com/problems/maximum-path-quality-of-a-graph/

Solution

Key to success in this problem is to read problem constraints carefully: I spend like 10 minutes before I understand that problem can be solved using very simple dfs. Why? Because it is given that maxTime <= 100 and time_j >= 10. It means that we can make no more than 10 steps in our graph! So, all we need to do is to run dfs(node, visited, gain, cost), where:

  1. node is current node we are in.
  2. visited is set of visited nodes: we need to keep set, because we count visitet nodes only once.
  3. gain is total gain we have so far.
  4. cost is how much time we still have.

Complexity

We have at most 10 steps, and it is also given that each node have at most degree 4, so in total we can make no more than 4^10 states. That is why we will not get TLE.

Code

class Solution:
    def maximalPathQuality(self, values, E, maxTime):
        G = defaultdict(list)
        for x, y, w in E:
            G[x].append((y, w))
            G[y].append((x, w))
            
        def dfs(node, visited, gain, cost):
            if node == 0: self.ans = max(self.ans, gain)
            for neib, w in G[node]:
                if w <= cost:
                    dfs(neib, visited | set([neib]), gain + (neib not in visited) * values[neib], cost - w)

        self.ans = 0
        dfs(0, set([0]), values[0], maxTime)
        return self.ans