Python | Easy | Graph | Maximum Path Quality of a Graph
\nsee the Successfully Accepted Submission\nPython\nclass Solution:\n    def maximalPathQuality(self, values, edges, maxTime):\n        n = len(values)\n       
\n[see the Successfully Accepted Submission](https://leetcode.com/submissions/detail/1071689029/)\n```Python\nclass Solution:\n    def maximalPathQuality(self, values, edges, maxTime):\n        n = len(values)\n        adj = [[] for _ in range(n)]\n\n        # Create an adjacency list to represent the graph with edges and time values.\n        for e in edges:\n            i, j, t = e[0], e[1], e[2]\n            adj[i].append((j, t))\n            adj[j].append((i, t))\n\n        res = [0]\n        seen = [0] * n\n        seen[0] += 1\n        # Start DFS traversal from node 0 with initial score values[0].\n        self.dfs(adj, 0, values, maxTime, seen, res, values[0])\n        return res[0]\n\n    def dfs(self, adj, src, values, maxTime, seen, res, score):\n        # If we return to the source node (node 0), update the result with the maximum score.\n        if src == 0:\n            res[0] = max(res[0], score)\n\n        # If we run out of time, return.\n        if maxTime < 0:\n            return\n\n        # Iterate through adjacent nodes.\n        for data in adj[src]:\n            dst, t = data[0], data[1]\n\n            # If we have enough time to reach the destination node, continue DFS.\n            if maxTime - t < 0:\n                continue\n\n            seen[dst] += 1\n            # Continue DFS to the destination node with updated score and remaining time.\n            self.dfs(adj, dst, values, maxTime - t, seen, res, score + (values[dst] if seen[dst] == 1 else 0))\n            seen[dst] -= 1\n```\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)\n\n
['Graph', 'Python']