Leetcode 1584: Min Cost to Connect All Points

 https://leetcode.com/problems/min-cost-to-connect-all-points/description/

Notes:

[udpate 2020-09-13]

In the first method (see below), we keep a very large priority queue, which actually is not necessary. 

Here is a better way to maintain the information in the spanning process. 

1): will use a vector to label whether a node is connected or not. (index for node, value for connected condition: 1 for connected, 0 for dis-connected);

2): will use a second vector to label the shortest distance for a dis-connected node to all the connected nodes. This needs to be updated when a new node becomes connected.

But the basic idea is the same: find the node (or point) having the shortest distance to the nodes already connected.

See the code below:

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        vector<int> used(n, 0), mxs(n, INT_MAX);
        mxs[0] = 0;
        for(int i=0; i<n; ++i) {
            // find the next node with the shortest distance
            int id = 0, mm = INT_MAX;
            for(int j=0; j<n; ++j) {
                if(!used[j] && mxs[j] < mm) {
                    id = j;
                    mm = mxs[j];
                }
            }
            used[id] = 1;
            res += mm;
            // update mxs (since a new element at id is added in, so just need to update the shortest dis to it)
            for(int j=0; j<n; ++j) {
                if(used[j]) continue;// if connected already, continue
                int dis = abs(points[id][0] - points[j][0]) + abs(points[id][1] - points[j][1]);
                if(dis < mxs[j]) mxs[j] = dis;
            }
        }
        return res;
    }
};

This is question can be viewed as a variation of minimum spanning tree. In some sense, it is also similar to Dijkstra algorithm.

Since eventually we need to connect all the nodes, so it does not matter starting with which one.

Similar to Dijkstra, we will have a connected pool: set, and the distance rank: a reversed priority queue.

Let start with points[0], 

1): then we will choose the point with the shortest distance with points[0] as the next one;

so a reversed priority_queue can be used;

2): after having the second points, we need to put all the distance from the second points to the rest points into the priority_queue;

3): the top of the priority_queue should always be the next points to be connected (this is exactly the same as Dijkstra)

4): after having the next points, we should update all the available distances into the priority_queue...

until all the nodes are connected.

Since we have a set to record the connected nodes, so we just can use this to avoid duplicated visiting.

See the code below:

class Solution {
public:
    typedef pair<int, int> pi;
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        set<int> st;
        st.insert(0);
        for(int i=1; i<n; ++i) {
            int dis = abs(points[0][0] - points[i][0]) + abs(points[0][1] - points[i][1]);
            pq.push({dis, i});
        }
        while(st.size() < n) {
            while(st.count(pq.top().second)) pq.pop();
            if(pq.empty()) break;
            auto t = pq.top();
            int d = t.first, id = t.second;
            res += d;
            // cout<<res<<" "<<d<<endl;
            st.insert(id);
            for(int i=0; i<n; ++i) {
                if(st.count(i)) continue;
                int dis = abs(points[id][0] - points[i][0]) + abs(points[id][1] - points[i][1]);
                pq.push({dis, i});
            }
        }
        return res;
    }
};