Leetcode Problem 1168. Optimize Water Distribution in a Village
Leetcode Solutions
Approach: Prim's Algorithm with Heap
- Create a virtual vertex (indexed as 0) and connect it to all houses with edges weighted by the cost of building wells.
- Initialize a min-heap to store edges based on their costs.
- Add all edges from the virtual vertex to the min-heap.
- Initialize a set to track vertices included in the MST.
- While the set does not contain all vertices: a. Pop the cheapest edge from the min-heap. b. If the edge connects a vertex outside the MST, add it to the MST and push all its adjacent edges to the min-heap.
- Sum up the costs of all edges in the MST to get the minimum total cost.
Approach: Kruskal's Algorithm with Union-Find
Ask Question
Programming Language
Purpose:
image/screenshot of info(optional)
Full Screen
Loading...
Suggested Answer
Answer
Full Screen
Copy Answer Code
Loading...