Optimize Water Distribution in a Village

Problem Id: 1168 Difficulty: Hard


Intuition

Solution


class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        # Build the graph
        graph = DiGraph(n)
        for p, q, weight in pipes:
            p, q = p - 1, q - 1
            graph.add_edge(p, q, weight)

        visited = [False] * n
        heap = []
        for index, cost in enumerate(wells):
            heapq.heappush(heap, [cost, index])

        total_cost = 0
        while heap:
            cost, vertex = heapq.heappop(heap)
            if visited[vertex]:
                continue
            visited[vertex] = True
            total_cost += cost
            for edge in graph.adj[vertex]:
                if not visited[edge.another(vertex)]:
                    heapq.heappush(heap, [edge.weight, edge.another(vertex)])
        return total_cost