💥💥 Beats 100% on runtime and memory [EXPLAINED]
Intuition\nFinding the best route through a graph, maximizing the quality of the path while staying within a specified travel time. Each node has a value that c
# Intuition\nFinding the best route through a graph, maximizing the quality of the path while staying within a specified travel time. Each node has a value that contributes to the total quality, and the goal is to visit nodes strategically to collect the highest possible quality without exceeding the time limit.\n\n# Approach\nUse a backtracking technique to explore all possible paths from the starting node, keeping track of the current travel time and quality, and updating the maximum quality whenever you return to the starting node.\n\n# Complexity\n- Time complexity:\nO(2^N), where N is the number of nodes, because each node can either be included in a path or not, creating many combinations.\n\n- Space complexity:\nO(N), due to the storage required for the recursive call stack and tracking visited nodes.\n\n# Code\n```typescript []\n// Define a type for the graph node structure\ntype TGraphNode = {\n    aNodes: number[]; // Array of connected nodes\n    aTimes: number[];  // Array of times to reach connected nodes\n};\n\n/**\n * Builds a graph represented as an array of nodes from given edges.\n * @param {number} n - The number of nodes in the graph.\n * @param {[number, number, number?][]} edges - An array of edges, where each edge is defined by [u, v, t].\n * @returns {TGraphNode[]} - An array of graph nodes where each node contains its connections and travel times.\n */\nfunction buildGraph(n: number, edges: [number, number, number?][]): TGraphNode[] {\n    // Initialize the nodes array\n    const nodes: TGraphNode[] = [];\n    for (let i = 0; i < n; i++) {\n        nodes.push({ aNodes: [], aTimes: [] });\n    }\n\n    // Loop through each edge to build the graph\n    const m = edges.length;\n    for (let i = 0; i < m; i++) {\n        const [u, v, t] = edges[i]; // Destructure the edge\n        nodes[u].aNodes.push(v);   // Add node v to u\'s adjacency list\n        nodes[u].aTimes.push(t!);   // Add travel time to u\'s adjacency list (using \'!\' for undefined)\n        nodes[v].aNodes.push(u);   // Add node u to v\'s adjacency list\n        nodes[v].aTimes.push(t!);   // Add travel time to v\'s adjacency list (using \'!\' for undefined)\n    }\n\n    return nodes; // Return the constructed graph\n}\n\n// Array to track the number of times each node is visited\nconst curUseds = new Uint8Array(1000);\n\n/**\n * Calculates the maximum path quality of a graph within a given time limit.\n * @param {number[]} values - An array of values associated with each node.\n * @param {[number, number, number][]} edges - An array of edges representing connections and their travel times.\n * @param {number} maxTime - The maximum allowed time for a path.\n * @returns {number} - The maximum quality of a valid path.\n */\nvar maximalPathQuality = function (values: number[], edges: [number, number, number][], maxTime: number): number {\n    const n = values.length; // Number of nodes\n    const g = buildGraph(n, edges); // Build the graph\n\n    let curTime = 0; // Current travel time\n    let curQual = 0; // Current path quality\n    let res = 0; // Resulting maximum quality\n    curUseds.fill(0, 0, n); // Reset usage tracker\n\n    // Backtracking function to explore paths\n    function bt(u: number) {\n        if (!curUseds[u]) curQual += values[u]; // Add value if it\'s the first visit\n        ++curUseds[u]; // Increment visit count\n\n        if (u === 0) res = Math.max(res, curQual); // Update result if back at start\n\n        const { aNodes, aTimes } = g[u]; // Get neighbors and travel times\n\n        // Explore all connected nodes\n        for (let i = 0; i < aNodes.length; ++i) {\n            if (aTimes[i] + curTime <= maxTime) { // Check if the path is within time limit\n                curTime += aTimes[i]; // Update current time\n                bt(aNodes[i]); // Recur for the next node\n                curTime -= aTimes[i]; // Backtrack time\n            }\n        }\n\n        --curUseds[u]; // Decrement visit count\n        if (!curUseds[u]) curQual -= values[u]; // Remove value if it was the last visit\n    }\n\n    bt(0); // Start backtracking from node 0\n    return res; // Return the maximum quality found\n};\n\n\n```
['Array', 'Backtracking', 'Graph', 'TypeScript']