<p>You are given an array <code>points</code> representing integer coordinates of some points on a 2D-plane, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>The cost of connecting two points <code>[x<sub>i</sub>, y<sub>i</sub>]</code> and <code>[x<sub>j</sub>, y<sub>j</sub>]</code> is the <strong>manhattan distance</strong> between them: <code>|x<sub>i</sub> - x<sub>j</sub>| + |y<sub>i</sub> - y<sub>j</sub>|</code>, where <code>|val|</code> denotes the absolute value of <code>val</code>.</p>

<p>Return <em>the minimum cost to make all points connected.</em> All points are connected if there is <strong>exactly one</strong> simple path between any two points.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/d.png" style="width: 214px; height: 268px;" />
<pre>
<strong>Input:</strong> points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
<strong>Output:</strong> 20
<strong>Explanation:</strong> 
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/c.png" style="width: 214px; height: 268px;" />
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> points = [[3,12],[-2,5],[-4,1]]
<strong>Output:</strong> 18
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 1000</code></li>
	<li><code>-10<sup>6</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li>All pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are distinct.</li>
</ul>

#define MOD 1000000007
#define pb push_back
#define _pb pop_back
#define vpii vector<pair<int, int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vvs vector<vector<string>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define ll long long
#define L left
#define R right
#define D data
#define V val
#define F first
#define S second
#define ii int, int
#define pii pair<int, int>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
#define max3_(a, b, c) (max(a, max(b, c)))
#define min3_(a, b, c) (min(a, min(b, c)))
#define addMod(a, b) (int)( (ll)(a)%MOD + (b)%MOD )%MOD
#define prdMod(a, b) (int)( (ll)(a)%MOD * (b)%MOD )%MOD
#define repIt(it, v) for(auto it=v.begin(); it!=v.end(); it++)
#define rep(i, a, b) for(i=a; i<b; i++)
#define rep_(i, a, b) for(int i=a; i<b; i++)
#define repr(i, b, a) for(i=b; i>=a; i--)
#define repr_(i, b, a) for(int i=b; i>=a; i--)
#define umap unordered_map
#define MIN INT_MIN
#define MAX INT_MAX
#define INF 0x3f3f3f3f
#define umap unordered_map
typedef long long i64;
const double eps = 1e-9;
const double Pi = 2.0 * acos(0.0);

class Solution {
public:
    /*
        minimum-cost spanning tree
        lets use Prim's Algo (d < dist[v])
    */
    int minCostConnectPoints(vector<vector<int>>& points) 
    {
        int n = points.size();
        if(n<=1) return 0;

        vb visited(n, 0);
        vi dist(n, INF);
        set<pii> st; // {dist[s], s};

        dist[0] = 0;
        st.insert({dist[0], 0});

        while(!st.empty())
        {
            pii t = *st.begin(); st.erase(st.begin());
            
            int d=0, u=t.S;
            
            if(visited[u]) continue;
            visited[u] = 1;

            rep_(v, 0, n)
            {
                if(u==v) continue;
                int x1=points[u][0], x2=points[v][0], y1=points[u][1], y2=points[v][1];
                d = abs(x1-x2) + abs(y1-y2);
                if(!visited[v] && (dist[v]==INF || d<dist[v]))
                {
                    dist[v] = d;
                    st.insert({dist[v], v});
                }
            }
        }

        int res = 0;
        rep_(i, 0, n) res += dist[i];

        return res;
    }
};
28755