LeetCode－1584. Min Cost to Connect All Points

 難度:Medium

描述:給一個名為 points 的數列，代表二維平面上一些點的整數座標，其中 points[i] = [xi, yi]。

 連接兩個點 [xi, yi] 和 [xj, yj] 的成本是它們之間的曼哈頓距離：|xi - xj| + |yi - yj|，其中 |val| 表示 val 的絕對值。 

返回使所有點連接的最小成本。

如果任意兩點之間僅存在一條簡單路徑，則所有點都是連接的。

方法：

最小成本生成樹(Minimum Spanning Tree，MST)

思路：

1.以0為起始點加入Set。

2.尋找Set 中Point連接的最短邊，將Point加入Set。

3.直到所有Point加入Set。

Time Complexity : O(n2)

Runtime : 166 ms         (80.41%)

Memory :  27.64 MB     (89.27%)

 

class Solution {
public:
    int calculateCost(vector<int>& p1,vector<int>& p2){
        return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int ans = 0;
        vector<vector<int>> costTable(points.size(), vector<int>(points.size(), 0));
        set<int> S;
        for(int i=0;i<points.size();++i){
            for(int j=i+1;j<points.size();++j){
                costTable[i][j] = costTable[j][i] = calculateCost(points[i],points[j]);
            }
        }
        S.insert(0);
        vector<int>& Scost = costTable[0];
        while(S.size()<points.size()){
            for(int i=1;i<points.size();++i){
                if(S.find(i)==S.end()){
                    int minE = INT_MAX;
                    int findNode = -1;
                    for(int j=0;j<points.size();++j){
                        if(S.find(j)!=S.end()){
                            continue;
                        }
                        if(Scost[j]<minE){
                            minE = Scost[j];
                            findNode = j;
                        }
                    }
                    S.insert(findNode);
                    ans += minE;
                    //update
                    for(int j=0;j<points.size();++j){
                        if(costTable[findNode][j]<Scost[j]){
                            Scost[j] = costTable[findNode][j];
                        }
                    }
                }
            }
        }
        return ans;
    }
};