aboutsummaryrefslogtreecommitdiff
path: root/min_cost_connect_points.cpp
blob: 09a00c36e7ac32e2ce2cbe861ec200f836f6d28b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include "leetcode.h"

class Solution {
public:
  int minCostConnectPoints(vector<vector<int>> &points) {
    int n = points.size();
    vector<vector<int>> cost(n, vector<int>(n));
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        cost[i][j] =
            abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
    int ans = solve(n, cost);
    return ans;
  }

private:
  int minNode(int n, int keyVal[], bool mstSet[]) {
    int mini = INT_MAX;
    int miniIdx = -1;
    for (int i = 0; i < n; i++)
      if (mstSet[i] == false && keyVal[i] < mini)
        mini = keyVal[i], miniIdx = i;
    return miniIdx;
  }
  int solve(int n, vector<vector<int>> &city) {
    int parent[n], keyVal[n];
    bool mstSet[n];
    for (int i = 0; i < n; i++) {
      keyVal[i] = numeric_limits<int>::max();
      mstSet[i] = false;
    }
    parent[0] = -1;
    keyVal[0] = 0;
    for (int i = 0; i < n - 1; i++) {
      int u = minNode(n, keyVal, mstSet);
      mstSet[u] = true;
      for (int j = 0; j < n; j++) {
        if (city[u][j] && mstSet[j] == false && city[u][j] < keyVal[j]) {
          keyVal[j] = city[u][j];
          parent[j] = u;
        }
      }
    }
    int cost = 0;
    for (int i = 1; i < n; i++)
      cost += city[parent[i]][i];
    return cost;
  }
};

int main() {}