1584. Min Cost to Connect All Points

similar to Dijsktra

just use Set and PQ

```java
class Solution {
    class Node {
        int id;
        int w;
        Node(int id, int w) {
            this.id = id;
            this.w = w;
        }
    }
    public int minCostConnectPoints(int[][] points) {
        Map<Integer, List<Node>> graph = buildGraph(points);
        Queue<Node> pq = new PriorityQueue<>((a, b) -> a.w - b.w);
        pq.offer(new Node(0, 0));
        Set<Integer> visited = new HashSet<>();

        int result = 0;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visited.contains(cur.id)) {
                continue;
            }
            visited.add(cur.id);
            result += cur.w;
            if (visited.size() == points.length) {
                return result;
            }
            
            if (graph.containsKey(cur.id)) {
                for (Node next : graph.get(cur.id)) {
                    pq.offer(next);
                }
            }
        }
        return -1;
    }
    private Map<Integer, List<Node>> buildGraph(int[][] points) {
        Map<Integer, List<Node>> graph = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            for (int j = i+1; j < points.length; j++) {
                int w = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                graph.putIfAbsent(i, new ArrayList<>());
                graph.get(i).add(new Node(j, w));
                graph.putIfAbsent(j, new ArrayList<>());
                graph.get(j).add(new Node(i, w));
            }
        }
        return graph;
    }
}
```

Last updated

Was this helpful?