C++ DFS
See my latest update in repo LeetCode\n## Solution 1. DFS\n\nSince 10 <= timej, maxTime <= 100, the path at most have 10 edges. Since each node at most has 4 ed
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n## Solution 1. DFS\n\nSince `10 <= timej, maxTime <= 100`, the path at most have `10` edges. Since each node at most has `4` edges, the maximum number of possible paths is `4^10 ~= 1e6`, so a brute force DFS should work.\n\n```cpp\n// OJ: https://leetcode.com/problems/maximum-path-quality-of-a-graph/\n// Author: github.com/lzl124631x\n// Time: O(4^10)\n// Space: O(V + E)\nclass Solution {\npublic:\n    int maximalPathQuality(vector<int>& V, vector<vector<int>>& E, int maxTime) {\n        int N = V.size();\n        vector<vector<pair<int, int>>> G(N); // build graph\n        for (auto &e : E) {\n            int u = e[0], v = e[1], c = e[2];\n            G[u].emplace_back(v, c);\n            G[v].emplace_back(u, c);\n        }\n        vector<int> cnt(N); // `cnt[u]` is the number of times we\'ve visted node `u` in the current path\n        int ans = 0;\n        function<void(int, int, int)> dfs = [&](int u, int val, int time) {\n            if (cnt[u] == 0) val += V[u];\n            cnt[u]++;\n            if (u == 0) ans = max(ans, val); // Only update answer if the current node is `0`.\n            for (auto &[v, c] : G[u]) {\n                if (time + c > maxTime) continue; // if the current time + the edge time is greater than maxTime, skip\n                dfs(v, val, time + c);\n            }\n            cnt[u]--;\n        };\n        dfs(0, 0, 0);\n        return ans;\n    }\n};\n```\n\nOr we can optionally add Dijkstra to backtrack earlier.\n\n```cpp\n// OJ: https://leetcode.com/problems/maximum-path-quality-of-a-graph/\n// Author: github.com/lzl124631x\n// Time: O(ElogE + 4^10)\n// Space: O(V + E)\nclass Solution {\n    typedef array<int, 2> T;\npublic:\n    int maximalPathQuality(vector<int>& V, vector<vector<int>>& E, int maxTime) {\n        int N = V.size();\n        vector<vector<array<int, 2>>> G(N); // build graph\n        for (auto &e : E) {\n            int u = e[0], v = e[1], c = e[2];\n            G[u].push_back({v, c});\n            G[v].push_back({u, c});\n        }\n        priority_queue<T, vector<T>, greater<T>> pq; // use Dijkstra to find the shortest distance from node 0 to all other nodes.\n        vector<int> dist(N, INT_MAX);\n        dist[0] = 0;\n        pq.push({0, 0});\n        while (pq.size()) {\n            auto [d, u] = pq.top();\n            pq.pop();\n            if (d > dist[u]) continue;\n            for (auto &[v, c] : G[u]) {\n                if (dist[v] > dist[u] + c) {\n                    dist[v] = dist[u] + c;\n                    pq.push({dist[v], v});\n                }\n            }\n        }\n        vector<int> cnt(N); // `cnt[u]` is the number of times we\'ve visted node `u` in the current path\n        int ans = 0;\n        function<void(int, int, int)> dfs = [&](int u, int val, int time) {\n            if (cnt[u] == 0) val += V[u];\n            cnt[u]++;\n            if (u == 0) ans = max(ans, val); // Only update answer if the current node is `0`.\n            for (auto &[v, c] : G[u]) {\n                if (time + c + dist[v] > maxTime) continue; // if the current time + the edge time + dist[u] is greater than maxTime, skip\n                dfs(v, val, time + c);\n            }\n            cnt[u]--;\n        };\n        dfs(0, 0, 0);\n        return ans;\n    }\n};\n```
[]