Naive DFS, backtrack, simple but my internet went off
Let\'s go directly to the data size, time >= 10 and maxTime <= 100. We will let it traverse at most 10 steps from 0. \nThe sentence, at most four edges for each
Let\'s go directly to the data size, `time >= 10` and `maxTime <= 100`. We will let it traverse at most 10 steps from 0. \nThe sentence, `at most four edges for each node`, indicate that we will have at most 4^10 steps to move in total which is\naround 10^6 to 10^7 steps. So searching in a brute force way should work on LeetCode...\n\nI use backtrack here as it\'s easier to mark qualities from unique nodes.\n\n```\nclass Solution {\npublic:\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        // 10 steps at most, 4 directions at most -> 4 ^ 10 -> 2 ^ 20\n        this->maxTime = maxTime;\n        this->n = values.size();\n        visited = vector<int>(1000, 0);\n        vector<vector<pair<int,int>>> graph(n);\n        for(vector<int>& vec : edges) {\n            graph[vec[0]].emplace_back(vec[1], vec[2]);\n            graph[vec[1]].emplace_back(vec[0], vec[2]);\n        }\n        \n        // run backtracking\n        visited[0] = 1;\n        backtrack(graph, values, 0, values[0], 0);\n        return res;\n    }\nprivate:\n    int res = 0;\n    int maxTime, n;\n    vector<int> visited;\n    void backtrack(vector<vector<pair<int,int>>>& graph, vector<int>& values, int curr, int quality, int time) {        \n        if(curr == 0) {\n            res = max(quality, res);\n        }\n        for(auto [v, t] : graph[curr]) {\n            if(time + t > maxTime) continue;\n            if(visited[v] > 0) // visited\n                backtrack(graph, values, v, quality, time + t);            \n            else {\n                visited[v] = 1;\n                backtrack(graph, values, v, quality + values[v], time + t);\n                visited[v] = 0;\n            }\n        } \n    }\n};\n```
[]