Connecting Cities by Grid — Solution & Editorial

Back to the Problem

Prim's algorithm on the complete Manhattan-distance graph is O(N²), sufficient here. (The specialized Manhattan-MST reduces the edge set to O(N) using 4-quadrant sweeps for N = 10⁵.)

Complexity: O(N²)

Watch out: Total cost reaches ~10⁹.