Growing one network from a point
When every pair of points could be joined, grow a single network outwards, always adding the nearest point not yet in it. About 16 minutes.
Grow one network
You have points on a map and can run a cable between any two, costing the Manhattan distance, which means the horizontal gap plus the vertical gap. Connect them all as cheaply as possible.
Start with one point as the network. For every other point, remember how close it is to the network. Repeat: pick the outsider that is closest, add it, and pay that distance. Adding it may bring some outsiders closer, so check each against the new member.
def dist(a, b):
dx = abs(a[0] - b[0])
dy = abs(a[1] - b[1])
return dx + dy- total
- 0
The network is just A. Distances to A: B is 4, C is 7, D is 14.
The loop
Do n minus 1 rounds. In each round, scan the outsiders for the one with the smallest near value. Add its distance to the total and mark it inside. Then for every other outsider, lower its near value if the new member is closer than anything in the network so far.
No sorting, and no heap needed, because scanning n points each round is already as cheap as keeping a heap would be when there are about n squared links anyway. The answer is the total after the last round.
near[j] = min(near[j], dist(pick, j))
A new point joins the network. What do you update?
- AEvery outsider's closest distance, if the new point is closer than what it had
- BNothing, since distances never change
- COnly the total, by adding all remaining distances
Show the answer
Every outsider's closest distance, if the new point is closer than what it had. The new member may be the nearest link for some outsiders.
Connect the points
points[i] = [x, y] is the position of a point on a map. You may run a cable between any two points, and a cable costs the Manhattan distance between them, which is |x1 − x2| + |y1 − y2|. Return the smallest total cable cost so that every point is connected to every other, directly or through other points.
points = [[0, 0], [2, 2], [3, 10], [5, 2]] → 16
1 ≤ points ≤ 500 · −10,000 ≤ x, y ≤ 10,000