[Java/C++] dfs with optimization
A straightforward idea is to try all paths from node 0 and calculate the max path quality for paths also end with node 0.\n\nOne optimization we can add is: onc
A straightforward idea is to try all paths from node `0` and calculate the `max path quality` for paths also end with node `0`.\n\nOne **optimization** we can add is: once we cannot return back to node `0`, we stop. The `min_time` required from any node to node `0` can be pre-computed using *Dijkstra algorithm*.\n\n**Time complexity**: `O(4^10)`\n\n**Note the constraints**: `10 <= time_j, maxTime <= 100` and There are at most **four** edges connected to each node..\nIt means the max levels of `dfs` search is `10`, and at each level we have maximum of `4` neighbouring nodes to try. \nSo the time complexity is: `O(4^10)`.\n\n**Java solution**\n```\npublic int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n    final int N = values.length;\n    List<List<int[]>> map = new ArrayList<>();\n    for (int i = 0; i < N; i++) {\n        map.add(new ArrayList<>());\n    }\n    for (int[] e : edges) {\n        map.get(e[0]).add(new int[]{e[1], e[2]});\n        map.get(e[1]).add(new int[]{e[0], e[2]});\n    }\n    \n    int[] minTimeToZero = bfs(map, N);\n    Set<Integer> visited = new HashSet<>();\n    visited.add(0);\n    int[] res = new int[]{0};\n    dfs(map, minTimeToZero, N, values, 0, maxTime, visited, res);\n    return res[0];\n}\n\nprivate void dfs(List<List<int[]>> map, int[] minTimeToZero, int N, int[] values, int cur, int maxTime, Set<Integer> visited, int[] res) {\n    if (cur == 0) {\n        int sum = 0;\n        for (int i : visited) {\n            sum += values[i];\n        }\n        res[0] = Math.max(res[0], sum);\n    }\n    \n    for (int[] nei : map.get(cur)) {\n        if (minTimeToZero[nei[0]] + nei[1] <= maxTime) {\n            boolean added = visited.add(nei[0]);\n            dfs(map, minTimeToZero, N, values, nei[0], maxTime - nei[1], visited, res);\n            if (added) {\n                visited.remove(nei[0]);\n            }\n        }\n    }\n}\n\nprivate int[] bfs(List<List<int[]>> map, int N) {\n    int[] minTimeToZero = new int[N];\n    Arrays.fill(minTimeToZero, Integer.MAX_VALUE);\n    PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));\n    q.offer(new int[]{0, 0});\n    minTimeToZero[0] = 0;\n    while (!q.isEmpty()) {\n        int[] cur = q.poll();\n        if (cur[1] > minTimeToZero[cur[0]]) {\n            continue;\n        }\n        for (int[] nei : map.get(cur[0])) {\n            if (nei[1] + cur[1] < minTimeToZero[nei[0]]) {\n                minTimeToZero[nei[0]] = nei[1] + cur[1];\n                q.offer(new int[]{nei[0], nei[1] + cur[1]});\n            }\n        }\n    }\n    return minTimeToZero;\n}\n```\n\n**C++ solution**\n```\nclass Solution {\npublic:\n    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {\n        const int N = values.size();\n        vector<unordered_map<int, int>> mp(N, unordered_map<int, int>());\n        for (const auto& e : edges) {\n            mp[e[0]][e[1]] = e[2];\n            mp[e[1]][e[0]] = e[2];\n        }\n        vector<int> min_time0 = bfs(mp, N);\n        unordered_set<int> visited;\n        visited.insert(0);\n        int res = 0;\n        dfs(mp, min_time0, values, 0, maxTime, visited, res);\n        return res;\n    }\nprivate:\n    void dfs(const vector<unordered_map<int, int>>& mp, const vector<int>& min_time0, const vector<int>& values, \n             int cur, int max_time, unordered_set<int>& visited, int& res) {\n        if (cur == 0) {\n            int sum = 0;\n            for (int i : visited) {\n                sum += values[i];\n            }\n            res = max(sum, res);\n        }\n        \n        for (const auto& [next, time] : mp[cur]) {\n            if (time + min_time0[next] <= max_time) {\n                bool added = visited.count(next) == 0;\n                visited.insert(next);\n                dfs(mp, min_time0, values, next, max_time - time, visited, res);\n                if (added) {\n                    visited.erase(next);\n                }\n            }\n        }\n    }\n    \n    vector<int> bfs(const vector<unordered_map<int, int>>& mp, const int N) {\n        vector<int> min_time0(N, INT_MAX);\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;\n        min_heap.push({0, 0});\n        min_time0[0] = 0;\n        while (!min_heap.empty()) {\n            pair cur = min_heap.top();\n            min_heap.pop();\n            for (const auto& [next, time] : mp[cur.second]) {\n                if (time + cur.first < min_time0[next]) {\n                    min_time0[next] = time + cur.first;\n                    min_heap.push({time + cur.first, next});\n                }\n            }\n        }\n        return min_time0;\n    }\n};\n```
[]