[C++] DFS
Logical Thinking\nSince each node\'s value can be added only once, we\'d better use Depth-First Search to solve this problem. So we start from node 0, and try a
<strong>Logical Thinking</strong>\n<p>Since each node\'s value can be added only once, we\'d better use <strong>Depth-First Search</strong> to solve this problem. So we start from node <code>0</code>, and try all possible paths (edges can be used more than once). Each time we come to a new node which is not counted before, update the current quality with its value. Whenever we come back to node <code>0</code>, update the answer with current quality. If current time is larger than the maximal time, stop the current path and try the next one.</p>\n\n\n<strong>C++</strong>\n\n```\n// Topic     : 2065. Maximum Path Quality of a Graph (https://leetcode.com/problems/maximum-path-quality-of-a-graph/)\n// Author    : YCX\n// Time      : O(max<int>(M + N, T / minE))\n// Space     : O(M + N)\n\n\nclass Solution {\npublic:\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        unordered_map<int, vector<pair<int, int>>> connect;\n        for (auto e : edges)\n        {\n            connect[e[0]].push_back({e[1], e[2]});\n            connect[e[1]].push_back({e[0], e[2]});\n        }\n        int n = values.size(), ans = 0;\n        vector<int> cal(n, 0);\n        cal[0] = 1;\n        dfs(0, connect, cal, values, values[0], maxTime, 0, ans);\n        return ans;\n    }\n    \nprivate: \n    void dfs(int start, unordered_map<int, vector<pair<int, int>>>& connect, vector<int>& cal, vector<int>& values, int curQuality, int maxTime, int curTime, int& ans)\n    {\n        if (curTime > maxTime)\n            return;\n        if (start == 0)\n            ans = max<int>(ans, curQuality);\n        for (auto i : connect[start])\n        {\n            if (cal[i.first] == 0)\n            {\n                cal[i.first] = 1;\n                dfs(i.first, connect, cal, values, curQuality + values[i.first], maxTime, curTime + i.second, ans);\n                cal[i.first] = 0;\n            }\n            else\n                dfs(i.first, connect, cal, values, curQuality, maxTime, curTime + i.second, ans);\n        }\n    }\n};\n```\n
['Depth-First Search', 'C']