C++ | DFS
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    // Graph represented as an adjacency list, where each node points to a list of pairs (neighbor, travel time)\n    vector<pair<int, int>> graph[1001];\n\n    // Depth-First Search (DFS) function to explore all paths\n    void dfs(int node, int currTime, int sum, int maxTime, int& ans, vector<int>& values) {\n        // Base case: if the current time exceeds the maximum allowed time, return\n        if (currTime > maxTime) {\n            return;\n        }\n\n        // If we are at the starting node and within the allowed time, update the answer\n        if (node == 0 && currTime <= maxTime) {\n            ans = max(ans, sum);\n        }\n\n        // Store the value of the current node and set it to 0 to avoid double-counting\n        int val = values[node];\n        values[node] = 0;\n\n        // Explore all neighboring nodes\n        for (auto& [nextNode, time] : graph[node]) {\n            if (currTime + time <= maxTime) {\n                // Recursive call to DFS for the next node\n                dfs(nextNode, currTime + time, sum + val, maxTime, ans, values);\n            }\n        }\n\n        // Restore the value of the current node before backtracking\n        values[node] = val;\n    }\n\n    // Function to calculate the maximal path quality\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        // Build the graph from the given edges\n        for (auto& edge : edges) {\n            graph[edge[0]].emplace_back(edge[1], edge[2]);\n            graph[edge[1]].emplace_back(edge[0], edge[2]);\n        }\n\n        // Initialize the answer and start DFS from node 0\n        int ans = 0;\n        dfs(0, 0, 0, maxTime, ans, values);\n\n        // Return the maximal path quality, considering the starting node\'s value\n        return max(ans, values[0]);\n    }\n};\n\n```
['C++']