aboutsummaryrefslogtreecommitdiff
path: root/min_cost_connect_points.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'min_cost_connect_points.cpp')
-rw-r--r--min_cost_connect_points.cpp51
1 files changed, 0 insertions, 51 deletions
diff --git a/min_cost_connect_points.cpp b/min_cost_connect_points.cpp
deleted file mode 100644
index 09a00c3..0000000
--- a/min_cost_connect_points.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#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() {}