<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 pb push_back
typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef pair<ll, pair<ll, ll>> pp_ll; //(cost,(v1,v2))
vector<p_ll> graph[1002];
ll V, E;
priority_queue<pp_ll, vector<pp_ll>, greater<pp_ll>> pq; // min value is on top


ll prims(ll src)
{
        while(!pq.empty())
    {
        pq.pop();
    }


    ll n1, n2, edge_count = 0;
    ll  cost;
    bool visited[V+5];
    for (ll j = 0; j < V+5; j++)
        visited[j] = false;
    ll total_cost=0;
    n1 = src;
    visited[src] = true;
    while (edge_count< V - 1)
    {

        for (ll i = 0; i < graph[n1].size(); i++)
        {
            n2 = graph[n1][i].second;
            cost = graph[n1][i].first;
            if (visited[n2] == false)
                pq.push(make_pair(cost, make_pair(n1, n2)));
        }

        n1 = pq.top().second.first;
        n2 = pq.top().second.second;
        cost = pq.top().first;
        
        if (visited[n1] && !visited[n2])
        {
            total_cost+=cost;
            visited[n2] = true;
            edge_count++;
        }
        n1 = n2;
        pq.pop();
    }
    return total_cost;
}

void addEdge(ll v1, ll cost, ll v2)
{
    graph[v1].pb(make_pair(cost, v2));
    graph[v2].pb(make_pair(cost, v1));
}

class Solution {
public:
    ll minCostConnectPoints(vector<vector<int>>& points) {
         for(int x=0;x<1002;x++ )
        {
            graph[x].clear();
        }
        V = points.size();
        E= V*(V-1)/2;
        for(ll i=0; i<V-1;i++)
        {
            for(ll j=i+1;j<V;j++)
            {
                ll a1=points[i][0],a2=points[i][1];
                ll b1=points[j][0],b2=points[j][1];

                ll cost = abs(a1-b1)+abs(a2-b2);
                addEdge(i,cost,j); 

            }
        }
        ll ans = prims(0);
        return ans;
        
    }
};

105395