解题思路

本题要求在花费不超过 x 的条件下，最小化所有路径权值的最大值。

核心观察

路径的权值上限 X 是否可行，可以通过贪心从后往前递推：

1. 对于终点 v，其所在路径的权值上限为 X，因此 a_v 必须不超过 X
2. 对于其他节点 u，从 u 出发的路径需要满足：a_u + max_child <= X
3. 从拓扑序的逆序递推，可以得到每个节点满足约束所需的最小点权
4. 计算总花费 sum(max(0, a_i - new_a_i) * c_i)，判断是否 <= x

算法步骤

1. 预处理拓扑序，建立反向图
2. 二分答案 X（上界可取所有 a_i 之和）
3. 对每个 X，从后往前递推计算每个节点的最小可行点权
4. 验证所需总花费是否 <= x
5. 二分找到最小的可行 X

时间复杂度

O((n + m) * log(sum a_i))，在 n <= 500 时完全可接受

参考实现 (Python)

import sys
from collections import deque, defaultdict

def solve():
    input = sys.stdin.readline
    n, m, x = map(int, input().split())
    a = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        g[u].append(v)
        indeg[v] += 1
    
    order = []
    q = deque([i for i in range(n) if indeg[i] == 0])
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    
    rg = defaultdict(list)
    for u in range(n):
        for v in g[u]:
            rg[v].append(u)
    
    def check(limit):
        need = [0] * n
        for u in reversed(order):
            max_child = 0
            for v in rg[u]:
                max_child = max(max_child, need[v])
            need[u] = max_child
            if need[u] + a[u] > limit:
                need[u] = limit - a[u]
                if need[u] < 0:
                    need[u] = 0
            else:
                need[u] = 0
        
        total_cost = 0
        for i in range(n):
            reduce = a[i] - need[i]
            if reduce > 0:
                total_cost += reduce * c[i]
                if total_cost > x:
                    return False
        return total_cost <= x
    
    lo, hi = 0, sum(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)

if __name__ == '__main__':
    solve()