Java | backtracking | Concise | O(4^10)
Backtracking with the length of the paths limited to 10 at most. The branch factor is 4. So Time O(4^10).\n\n\nclass Solution {\n    Map<Integer, Map<Integer, I
Backtracking with the length of the paths limited to 10 at most. The branch factor is 4. So Time O(4^10).\n\n```\nclass Solution {\n    Map<Integer, Map<Integer, Integer> > g = new HashMap();\n    int res = 0;\n    int[] values;\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        this.values = values;\n        for(int[] e : edges) {\n            int u = e[0], v = e[1], t = e[2];\n            g.computeIfAbsent(u, x -> new HashMap()).put(v, t);\n            g.computeIfAbsent(v, x -> new HashMap()).put(u, t);\n        }\n        dfs(new ArrayList(), 0, maxTime, 0);\n        return res;\n    }\n    void dfs(List<Integer> path, int cur, int maxTime, int time) {\n        path.add(cur);\n        if(cur == 0) {\n            int tmp = 0;\n            Set<Integer> hs = new HashSet();\n            for(int i : path) {\n                if(hs.add(i)) tmp += values[i];\n            }\n            res = Math.max(res, tmp);\n        }\n        for(var en : g.getOrDefault(cur, new HashMap<>()).entrySet()) {\n            int nei = en.getKey(), t = en.getValue();\n            if(t + time > maxTime) continue;\n            dfs(path, nei, maxTime, t + time);\n        }\n        path.remove(path.size() - 1);\n    }\n}\n```
['Backtracking', 'Depth-First Search', 'Java']