Prims

mail@pastecode.io avatar
unknown
c_cpp
a year ago
893 B
2
Indexable
Never
class Solution {
    public:
        int minCostConnectPoints(vector<vector<int>>& points) {
            vector<bool> vis(points.size(), false);
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
            pq.push({0, 0});
            int ans = 0, edges = 0;
            while(edges < points.size()) {
                pair<int, int> p = pq.top();
                pq.pop();

                if(vis[p.second]) continue;
                vis[p.second] = true;
                ans += p.first;
                edges++;

                for(int i = 0; i < points.size(); i++) {
                    if(!vis[i]) {
                        pq.push({abs(points[p.second][0] - points[i][0]) + abs(points[p.second][1] - points[i][1]), i});
                    }
                }
            }

            return ans;
        }
    };