#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
int minCostConnectPoints(int **points, int pointsSize, int *pointsColSize) {
(void)pointsColSize; // always 2
int n = pointsSize;
int *minCost = malloc(n * sizeof(int));
bool *inTree = calloc(n, sizeof(bool));
for (int i = 0; i < n; i++)
minCost[i] = INT_MAX;
minCost[0] = 0;
int cost = 0;
for (int step = 0; step < n; step++) {
// 1. Pick the cheapest point not yet in the tree
int u = -1;
for (int i = 0; i < n; i++)
if (!inTree[i] && (u == -1 || minCost[i] < minCost[u]))
u = i;
// 2. Add it
inTree[u] = true;
cost += minCost[u];
// 3. Update the outside points' best connection
for (int i = 0; i < n; i++) {
if (inTree[i])
continue;
int dist =
abs(points[i][0] - points[u][0]) + abs(points[i][1] - points[u][1]);
if (dist < minCost[i])
minCost[i] = dist;
}
}
free(minCost);
free(inTree);
return cost;
}
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
class Solution {
public:
int minCostConnectPoints(vector<vector<int>> &points) {
int n = points.size();
vector<int> minCost(n, INT_MAX);
vector<bool> inTree(n, false);
minCost[0] = 0;
int cost = 0;
for (int step = 0; step < n; step++) {
// 1. Pick the cheapest point not yet in the tree
int u = -1;
for (int i = 0; i < n; i++)
if (!inTree[i] && (u == -1 || minCost[i] < minCost[u]))
u = i;
// 2. Add it
inTree[u] = true;
cost += minCost[u];
// 3. Update the outside points' best connection
for (int i = 0; i < n; i++) {
if (inTree[i])
continue;
int dist =
abs(points[i][0] - points[u][0]) + abs(points[i][1] - points[u][1]);
minCost[i] = min(minCost[i], dist);
}
}
return cost;
}
};
package graphs
import "math"
func minCostConnectPoints(points [][]int) int {
n := len(points)
minCost := make([]int, n)
inTree := make([]bool, n)
for i := range minCost {
minCost[i] = math.MaxInt
}
minCost[0] = 0
cost := 0
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
for step := 0; step < n; step++ {
// 1. Pick the cheapest point not yet in the tree
u := -1
for i := 0; i < n; i++ {
if !inTree[i] && (u == -1 || minCost[i] < minCost[u]) {
u = i
}
}
// 2. Add it
inTree[u] = true
cost += minCost[u]
// 3. Update the outside points' best connection
for i := 0; i < n; i++ {
if inTree[i] {
continue
}
dist := abs(points[i][0]-points[u][0]) + abs(points[i][1]-points[u][1])
minCost[i] = min(minCost[i], dist)
}
}
return cost
}
import java.util.Arrays;
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
int[] minCost = new int[n];
boolean[] inTree = new boolean[n];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[0] = 0;
int cost = 0;
for (int step = 0; step < n; step++) {
// 1. Pick the cheapest point not yet in the tree
int u = -1;
for (int i = 0; i < n; i++)
if (!inTree[i] && (u == -1 || minCost[i] < minCost[u]))
u = i;
// 2. Add it
inTree[u] = true;
cost += minCost[u];
// 3. Update the outside points' best connection
for (int i = 0; i < n; i++) {
if (inTree[i])
continue;
int dist = Math.abs(points[i][0] - points[u][0]) + Math.abs(points[i][1] - points[u][1]);
minCost[i] = Math.min(minCost[i], dist);
}
}
return cost;
}
}
/**
* @param {number[][]} points
* @return {number}
*/
var minCostConnectPoints = function (points) {
const n = points.length;
const minCost = new Array(n).fill(Infinity);
const inTree = new Array(n).fill(false);
minCost[0] = 0;
let cost = 0;
for (let step = 0; step < n; step++) {
// 1. Pick the cheapest point not yet in the tree
let u = -1;
for (let i = 0; i < n; i++)
if (!inTree[i] && (u === -1 || minCost[i] < minCost[u])) u = i;
// 2. Add it
inTree[u] = true;
cost += minCost[u];
// 3. Update the outside points' best connection
for (let i = 0; i < n; i++) {
if (inTree[i]) continue;
const dist = Math.abs(points[i][0] - points[u][0]) + Math.abs(points[i][1] - points[u][1]);
minCost[i] = Math.min(minCost[i], dist);
}
}
return cost;
};
from typing import List
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
min_cost = [float("inf")] * n
in_tree = [False] * n
min_cost[0] = 0
cost = 0
for _ in range(n):
# 1. Pick the cheapest point not yet in the tree
u = -1
for i in range(n):
if not in_tree[i] and (u == -1 or min_cost[i] < min_cost[u]):
u = i
# 2. Add it
in_tree[u] = True
cost += min_cost[u]
# 3. Update the outside points' best connection
ux, uy = points[u]
for i in range(n):
if in_tree[i]:
continue
dist = abs(points[i][0] - ux) + abs(points[i][1] - uy)
min_cost[i] = min(min_cost[i], dist)
return cost
impl Solution {
pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut min_cost = vec![i32::MAX; n];
let mut in_tree = vec![false; n];
min_cost[0] = 0;
let mut cost = 0;
for _ in 0..n {
// 1. Pick the cheapest point not yet in the tree
let u = (0..n)
.filter(|&i| !in_tree[i])
.min_by_key(|&i| min_cost[i])
.unwrap();
// 2. Add it
in_tree[u] = true;
cost += min_cost[u];
// 3. Update the outside points' best connection
for i in 0..n {
if in_tree[i] {
continue;
}
let dist = (points[i][0] - points[u][0]).abs() + (points[i][1] - points[u][1]).abs();
min_cost[i] = min_cost[i].min(dist);
}
}
cost
}
}