iT邦幫忙

2023 iThome 鐵人賽

DAY 15
0
自我挑戰組

leetcode題目分享系列 第 15

[Day 15] 1584. Min Cost to Connect All Points

  • 分享至 

  • xImage
  •  

參加鐵人賽後,才知自己的coding skill 如此 weak, 看50行的程式碼看了2小時......
這題運用Prim's algorithm,屬於minimum spanning tree的algo。
選擇起點,用min heap及hash table對比所有可連接的線後,選擇最短的distance

ref:https://leetcode.com/problems/min-cost-to-connect-all-points/solutions/4045874/94-85-prim-kruskal-with-min-heap/?envType=daily-question&envId=2023-09-15

int manhattan_distance(vector<int>& p1, vector<int>& p2) {
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);
}

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<bool> visited(n, false);
        unordered_map<int, int> heap_dict;
        for(int i = 0; i < n; ++i) {
            heap_dict[i] = INT_MAX; // Initialize all distances to infinity
        }
        heap_dict[0] = 0; // Start node
        
        auto cmp = [](pair<int, int> left, pair<int, int> right) { return left.first > right.first; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> min_heap(cmp);
        min_heap.push({0, 0});
        
        int mst_weight = 0;
        
        while (!min_heap.empty()) {
            auto [w, u] = min_heap.top();
            min_heap.pop();
            
            if (visited[u] || heap_dict[u] < w) continue;
            
            visited[u] = true;
            mst_weight += w;
            
            for (int v = 0; v < n; ++v) {
                if (!visited[v]) {
                    int new_distance = manhattan_distance(points[u], points[v]);
                    if (new_distance < heap_dict[v]) {
                        heap_dict[v] = new_distance;
                        min_heap.push({new_distance, v});
                    }
                }
            }
        }
        
        return mst_weight;
    }
};

上一篇
[Day 14] 332. Reconstruct Itinerary
下一篇
[Day 16] 1631. Path With Minimum Effort
系列文
leetcode題目分享30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言