Leetcode1584

class Solution {
public:
    int prim(vector<vector<int> >& points, int start) {
        int n = points.size();
        int res = 0;
        int inf=0x3f3f3f3f;
        // 1. 将points转化成邻接矩阵, 这一步可有可无
        int g[1005][1005];
        int dist[1005];
        bool st[1005];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                g[i][j] = dist;
                g[j][i] = dist;
            }
        }
        memset(dist, 0x3f, sizeof dist);
        memset(st,false,sizeof st);
        for (int i = 0; i < n; i ++ )
        {
            int t = -1;
            for (int j = 0; j < n ; j ++ )
                //!st[j]表示的是这个点没有被用过
                //(t == -1 || dist[t] > dist[j])代表的是要么是第一次开始找（也就是t == -1，此时不存在dist[t] > dist[j]）的情况，要么找到了一个点j，集合到点j的距离小于到t的距离，就更新t
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
            if (i) res += dist[t];
            st[t] = true;

            for (int j = 0; j < n; j ++ ) dist[j] = min(dist[j], g[t][j]);
        }
        return res;

    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        return prim(points, 0);  
    }
};