題目鏈接

給你一個points 數(shù)組，表示 2D 平面上的一些點，其中 points[i] = [xi, yi] 。

連接點 [xi, yi] 和點 [xj, yj] 的費用為它們之間的 曼哈頓距離 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的絕對值。

請你返回將所有點連接的最小總費用。只有任意兩點之間 有且僅有 一條簡單路徑時，才認為所有點都已連接。

示例 1：

輸入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 輸出：20

解釋：

我們可以按照上圖所示連接所有點得到最小總費用，總費用為 20 。
注意到任意兩個點之間只有唯一一條路徑互相到達。

示例 2：

輸入：points = [[3,12],[-2,5],[-4,1]] 輸出：18

示例 3：

輸入：points = [[0,0],[1,1],[1,0],[-1,1]] 輸出：4

示例 4：

輸入：points = [[-1000000,-1000000],[1000000,1000000]] 輸出：4000000

示例 5：

輸入：points = [[0,0]] 輸出：0

最小生成樹模板，建圖后套一個 prim 算法即可，AC代碼如下：

class Solution { public:int d[1005], vis[1005], g[1005][1005];unordered_map<int, vector<int>> mp;int dis(vector<int> &a, vector<int> &b) {return abs(a[0] - b[0]) + abs(a[1] - b[1]);}void build(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {g[i][j] = dis(mp[i], mp[j]);}}}int prim(int n) {fill(d, d + 1005, 1e9);d[0] = 0;int ans = 0;for (int i = 0; i < n; i++) {int u = -1, MIN = 1e9;for (int j = 0; j < n; j++) {if (!vis[j] && d[j] < MIN) {u = j;MIN = d[j];}}if (u == -1) return -1;vis[u] = 1;ans += d[u];for (int v = 0; v < n; v++) {if (g[u][v] < d[v] && !vis[v] && g[u][v] != 1e9) d[v] = g[u][v];}}return ans;}int minCostConnectPoints(vector <vector<int>> &points) {int n = points.size();for (int i = 0; i < n; i++) mp[i] = points[i];build(n);return prim(n);} };

總結

以上是生活随笔為你收集整理的LeetCode 1584 连接所有点的最小费用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。