解题思路

使用二分答案 + 拓扑序DP贪心验证。

算法步骤

1. 二分最大路径权值上限 X
2. 验证函数 check(X)：从后往前递推每个节点需要减多少权值才能满足约束
3. 统计总花费是否 ≤ x

正确性证明

（略）

参考代码（C++17）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    ll x;
    if(!(cin >> n >> m >> x)) return 0;
    vector<ll> a(n + 1), c(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    
    vector<vector<int>> g(n + 1), rg(n + 1);
    vector<int> indeg(n + 1, 0);
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        rg[v].push_back(u);
        indeg[v]++;
    }
    
    auto check = [&](ll limit) -> bool {
        vector<ll> need(n + 1, 0);
        queue<int> q;
        for(int i = 1; i <= n; i++)
            if(indeg[i] == 0) q.push(i);
        
        ll total = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            ll cur = max(0LL, need[u]);
            if(a[u] + cur > limit) {
                ll dec = a[u] + cur - limit;
                if(dec * c[u] > x) return false;
                total += dec * c[u];
                if(total > x) return false;
            }
            for(int v : g[u]) {
                need[v] = max(need[v], need[u]);
                if(--indeg[v] == 0) q.push(v);
            }
        }
        return total <= x;
    };
    
    // Restore indeg
    for(int i = 1; i <= n; i++)
        for(int v : g[i]) indeg[v]++;
    
    ll lo = 0, hi = 1e18;
    while(lo < hi) {
        ll mid = (lo + hi) / 2;
        if(check(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}