寻找解决方案 - 有向无环图问题

Question

在给定的 DAG 中，假设每个节点都有一个成本参数，并且每条边都有一个距离。 我们需要编写最小化函数是 MAX（所有选定节点的总成本，max（每个选定节点与其后代选定节点之间的距离之和）。

解决方案可以是任何语言。

写了这段代码。不确定这是否是最优化的解决方案

def minimize_max_cost(dag):
    # find the lower and upper bounds of the binary search
    lower_bound = float('inf')
    upper_bound = 0
    for node in dag:
        lower_bound = min(lower_bound, node.cost)
        upper_bound += node.cost

    # binary search for the minimum value of the function
    answer = float('inf')
    while lower_bound <= upper_bound:
        mid = (lower_bound + upper_bound) // 2
        total_cost = 0
        max_distance = 0
        for node in dag:
            if node.cost <= mid:
                total_cost += node.cost
                for child in node.children:
                    if child.cost <= mid:
                        max_distance = max(max_distance, node.distance_to(child))
        if max_distance <= mid:
            answer = min(answer, total_cost)
            upper_bound = mid - 1
        else:
            lower_bound = mid + 1

    return answer