在 C++ 中找到连接每个笛卡尔坐标的最小成本的程序

假设我们有一个二维笛卡尔坐标点 (x, y) 的列表。我们可以连接 (x0, y0) 和 (x1, y1)，其代价是 |x0 - x1| + |y0 - y1|。如果我们被允许连接任意数量的点，我们必须找到必要的最小成本，以便每个点都通过一条路径连接。

所以，如果输入像 points = [[0, 0],[0, 2],[0, -2],[2, 0],[-2, 0], [2, 3], [2 , -3]],

那么输出将为 14，因为从 (0, 0) 到 (0, 2),(0, -2),(2, 0),(-2, 0)，成本为 2，总计为 8，并且(2, 3) 最接近 (0, 2)，成本为 |2+1| = 3，对于 (2, -3)，它最接近 (0, -2)，成本也是 3。所以总成本是 8 + 6 = 14。

示例

让我们看看以下实现以更好地理解 -

#include <iostream>
#include <vector>
#define MAX 99999
using namespace std;

int interval(int i, int j, vector<vector<int>>& p) {
   return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}

int solve(vector<vector<int>>& p) {
   int n = p.size(), cost = 0;
   if (n < 2) return 0;

   vector<int> distance(n, MAX);
   vector<bool> visited(n);

   distance[0] = 0;

   for (int i = 0; i < n; i++) {
      int min_d = MAX, node = 0;
      for (int j = 0; j < n; j++) {
         if (!visited[j] && distance[j] < min_d) {
            min_d = distance[j];
            node = j;
         }
      }

      visited[node] = true;
      cost += distance[node];

      for (int j = 0; j < n; j++) {
         if (!visited[j]) {
            int d = interval(node, j, p);
            distance[j] = min(distance[j], d);
         }
      }
   }
   return cost;
}

int main(){
   vector<vector<int>> points = {{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}};
cout << solve(points);
}

输入

{{0, 0},{0, 2},{0, -2},{2, 0},{-2, 0}, {2, 3}, {2, -3}}

14