# @l2g 2065 python3
# [2065] Maximum Path Quality of a Graph
# Difficulty: Hard
# https://leetcode.com/problems/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.
# Example 4:
#
#
# Input: values = [0,1,2], edges = [[1,2,10]], maxTime = 10
# Output: 0
# Explanation:
# The only path is 0. The total time taken is 0.
# The only node visited is 0, giving a maximal path quality of 0.
#
#
# Constraints:
#
# n == values.length
# 1 <= n <= 1000
# 0 <= values[i] <= 10^8
# 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.
#
#

import heapq
from typing import List


class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        node_map = defaultdict(list)
        for s, e, t in edges:
            node_map[s].append([e, t])
            node_map[e].append([s, t])

        # get minimum time from node to 0
        heap = [[0, 0]]
        min_dist = dict()
        while heap:
            time, cur_node = heapq.heappop(heap)
            if cur_node not in min_dist:
                min_dist[cur_node] = time

                for next_node, travel_time in node_map[cur_node]:
                    heapq.heappush(heap, [time + travel_time, next_node])

        q = deque()
        q.append([0, maxTime, set([0]), values[0]])
        ans = -float("inf")
        while q:
            # print(q)
            cur_node, time_rem, visited, max_value = q.popleft()

            if time_rem >= min_dist[cur_node]:
                ans = max(ans, max_value)
            else:
                continue

            for next_node, travel_time in node_map[cur_node]:
                new_max = max_value + values[next_node] * (1 - int(next_node in visited))
                q.append([next_node, time_rem - travel_time, visited | set([next_node]), new_max])
        return ans


if __name__ == "__main__":
    import os

    import pytest

    pytest.main([os.path.join("tests", "test_2065.py")])
