그래프의 최대 경로 품질

n에서 0(포함)까지 번호가 매겨진 n - 1 노드가 있는 무향 그래프가 있습니다. 인덱스가 0인 정수 배열values이 제공됩니다. 여기서 values[i]는 ith 노드의 값입니다. 또한 인덱스가 0인 2D 정수 배열edges이 제공됩니다. 여기서 각 edges[j] = [uj, vj, timej]는 노드uj와 vj 사이에 무방향 에지가 있음을 나타내며 두 ​​노드 사이를 이동하는 데 timej초가 걸립니다. 노드. 마지막으로 정수maxTime가 제공됩니다.

그래프의 유효한 경로는 node 0 에서 시작하여 node 0 에서 끝나고 완료하는 데 최대 maxTime초가 걸리는 모든 경로입니다. 동일한 노드를 여러 번 방문할 수 있습니다. 유효한 경로의 품질은 경로에서 방문한 고유한 노드 값의 합계입니다(각 노드의 값은 최대 한 번 합계에 추가됨).

유효한 경로의 최대 품질을 반환합니다.

참고: 각 노드에 연결되는 에지는 최대 4개입니다.

예 1:



입력: 값 = [0,32,10,43], 에지 = [[0,1,10],[1,2,15],[0,3,10]], 최대 시간 = 49
출력: 75
설명:
한 가지 가능한 경로는 0 -> 1 -> 0 -> 3 -> 0입니다. 총 소요 시간은 10 + 10 + 10 + 10 = 40 <= 49입니다.
방문한 노드는 0, 1, 3이며 최대 경로 품질은 0 + 32 + 43 = 75입니다.

예 2:



입력: 값 = [5,10,15,20], 에지 = [[0,1,10],[1,2,10],[0,3,10]], 최대 시간 = 30
출력: 25
설명:
가능한 경로는 0 -> 3 -> 0입니다. 총 소요 시간은 10 + 10 = 20 <= 30입니다.
방문한 노드는 0과 3이며 최대 경로 품질은 5 + 20 = 25입니다.

예 3:



입력: 값 = [1,2,3,4], 가장자리 = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], 최대 시간 = 50
출력: 7
설명:
한 가지 가능한 경로는 0 -> 1 -> 3 -> 1 -> 0입니다. 총 소요 시간은 10 + 13 + 13 + 10 = 46 <= 50입니다.
방문한 노드는 0, 1, 3이며 최대 경로 품질은 1 + 2 + 4 = 7입니다.

제약:

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

모든 쌍[uj, vj]이 고유합니다.

각 노드에 연결된 에지는 최대 4개입니다.

그래프가 연결되지 않을 수 있습니다.

해결책:

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