Dijskra (beat 95%)
Code\njava []\nclass Solution {\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        Node[] nodes = new Node[values.length];\
# Code\n```java []\nclass Solution {\n    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {\n        Node[] nodes = new Node[values.length];\n        for (int i = 0; i < values.length; i++) {\n            nodes[i] = new Node(i, values[i]);\n        }\n        for (int[] e: edges) {\n            Node a = nodes[e[0]], b = nodes[e[1]];\n            a.edges.put(b, e[2]);\n            b.edges.put(a, e[2]);\n        }\n\n        int maxQuality = 0;\n        PriorityQueue<Path> pq = new PriorityQueue<>();\n        pq.add(new Path(nodes[0]));\n        while (!pq.isEmpty()) {\n            Path p = pq.poll();\n            if (!p.to.foundNodeSet.add(p.visitedNodes)) {\n                continue;\n            }\n            if (p.to == nodes[0]) {\n                int sum = 0;\n                for (Node n: p.visitedNodes) sum += n.value;\n                maxQuality = Math.max(maxQuality, sum);\n            }\n            for (Map.Entry<Node, Integer> e: p.to.edges.entrySet()) {\n                Node to = e.getKey();\n                int len = p.len + e.getValue();\n                if (len > maxTime) continue;\n                Path np = new Path(p, to, len);\n                pq.add(np);\n            }\n        }\n        return maxQuality;\n    }\n\n    static class Node {\n        int idx, value;\n        Map<Node, Integer> edges = new HashMap<>();\n        Set<Set<Node>> foundNodeSet = new HashSet<>();\n\n        public Node(int i, int v) {\n            idx = i; value = v;\n        }\n\n        public String toString() {\n            return String.format("(%d %d)", idx, value);\n        }\n    }\n\n    static class Path implements Comparable<Path>{\n        int len;\n        Node to;\n        Set<Node> visitedNodes;\n\n        public Path(Node zero) {\n            this.to = zero;\n            this.visitedNodes = Set.of(zero);\n        }\n\n        public Path(Path prev, Node to, int len) {\n            this.to = to;\n            this.len = len;\n            this.visitedNodes = new HashSet<>(prev.visitedNodes);\n            this.visitedNodes.add(to);\n        }\n\n        public int compareTo(Path p) {\n            return len - p.len;\n        }\n    }\n}\n```
['Java']