Java BFS with DP
Intuition\nBFS with dp\n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time complexity:\n Add your time complexity here, e.g.
# Intuition\nBFS with dp\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    class Node {\n        int num;\n        int time;\n        int quality;\n        HashSet<Integer> set;\n        Node(int a,int b,int c, HashSet<Integer> s){\n            num = a;\n            time= b;\n            quality=c;\n            set=s;\n        }\n    }\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        int n = values.length;\n        HashMap<Integer,ArrayList<int[]>> graph = new HashMap<>();\n        for(int i=0;i<n;i++){\n            graph.put(i,new ArrayList<>());\n        }\n        for(int i=0;i<edges.length;i++){\n            ArrayList<int[]> arr = graph.get(edges[i][0]);\n            arr.add(new int[]{edges[i][1],edges[i][2]});\n\n            arr = graph.get(edges[i][1]);\n            arr.add(new int[]{edges[i][0],edges[i][2]});\n        }\n        HashMap<Integer,int[]> visited = new HashMap<>();\n        \n        Queue<Node> pq = new LinkedList<>();\n        HashSet<Integer> set = new HashSet<>();\n        set.add(0);\n        pq.add(new Node(0,0,values[0],set));\n        int maxQuality=Integer.MIN_VALUE;\n        while(!pq.isEmpty()){\n\n            Node ele= pq.poll();\n            if(visited.containsKey(ele.num)){\n                int[] dp = visited.get(ele.num);\n                if(dp[0]<= ele.time && dp[1]> ele.quality){\n                    continue;\n                }\n            }\n            visited.put(ele.num,new int[]{ele.time,ele.quality});\n            if(ele.num==0){\n                maxQuality=Math.max(maxQuality,ele.quality);\n            }\n            for(int[]child:graph.get(ele.num)){\n                HashSet<Integer> newSet = (HashSet)ele.set.clone();\n                int newQuality = ele.quality;\n                if(ele.time+child[1]<=maxTime){\n                    if(!newSet.contains(child[0])){\n                        newSet.add(child[0]);\n                        newQuality+= values[child[0]];\n                    }\n                    \n                    pq.add(new Node(child[0],ele.time+child[1], newQuality, newSet));\n                }\n            }\n        }\n        return maxQuality;\n    }\n}\n```
['Java']