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?