Maximum Path Quality of a Graph LeetCode solution in Python

1
class Solution:
2
    def maximalPathQuality(
3
        self, values: List[int], edges: List[List[int]], maxTime: int
4
    ) -> int:
5
        graph = defaultdict(list)
6
        # build graph
7
        for edge in edges:
8
            graph[edge[0]].append((edge[1], edge[2]))
9
            graph[edge[1]].append((edge[0], edge[2]))
10

11
        q = deque()
12
        q.append((0, 0, values[0], set([0])))
13
        cache = {}
14
        maxPoint = 0
15

16
        while q:
17
            currV, currTime, currPoints, currSet = q.popleft()
18
            if currV in cache:
19
                # if vertex has been visited, and if the previousTime is
20
                # less or equal to current time but current points is lower?
21
                # then this path can't give us better quality so stop proceeding.
22
                prevTime, prevPoints = cache[currV]
23
                if prevTime <= currTime and prevPoints > currPoints:
24
                    continue
25
            cache[currV] = (currTime, currPoints)
26
            # can't go over the maxTime limit
27
            if currTime > maxTime:
28
                continue
29
            # collect maxPoint only if current vertex is 0
30
            if currV == 0:
31
                maxPoint = max(maxPoint, currPoints)
32
            for neigh, neighTime in graph[currV]:
33
                newSet = currSet.copy()
34
                # collects quality only if not collected before
35
                if neigh not in currSet:
36
                    newSet.add(neigh)
37
                    newPoint = currPoints + values[neigh]
38
                else:
39
                    newPoint = currPoints
40
                q.append((neigh, currTime + neighTime, newPoint, newSet))
41
        return maxPoint