解题思路与方法

题意回顾与抽象

• 有 $n$ 个营地（1 到 $n$），从 1 出发到 $n$ 结束。
• 到达营地 $i$ 时可把携带的“补给包数量”增加不超过 $A_i$ 个（不能减少），并且“之前带上的包都会被补满”（这只影响“内容”，不影响“数量”）。
• 单向边 $(u\to v)$ 需要当前携带数量 $\ge W_{uv}$ 才能走。
• 初始在 1，携带 0 个。目标：能到 $n$，且到达时携带数量最小。

等价地把携带的包当作一个非减的数值序列；在每个营地最多再拿 $A_i$ 个；每条边要求当前数值 $\ge W$。

关键算法：二分答案 + DAG 上的可行性检查（贪心/DP）

由于“最终到达时携带的数量 $K$”越大越容易可行，存在单调性：若 $K$ 可行，则任何 $K'>K$ 也可行。可以二分最优答案。

1. 可行性检查 check(K)（按编号顺序的 DP/贪心） 给定上限 $K$，定义

   $s[i] =$$\text{在上限 }$$K\text{ 下，到达营地 }i\text{ 时可达到的最大携带数}$

   • 初始化：$s[1] = \min(K, A_1)$，其余 $s[i]=-1$ 表示不可达（起点携带 0，最多加 $A_1$，且不能超过上限 $K$）。

   • 由于保证 $u < v$，图是 DAG，可按 $i=1..n$ 递增：

     • 若 $s[i] < 0$ 跳过；
     • 对每条出边 $(i\to j, W)$，只有当 $s[i]\ge W$ 才能走；
     • 抵达 $j$ 后可再拿不超过 $A_j$，且受上限 $K$ 约束： $s[j] \gets \max\big(s[j],$$\min(K,\,$$s[i]+A_j)\big)$

   • 最终 $s[n]\ge 0$ 表示在上限 $K$ 内可达。

   贪心地“把能拿的都拿满（受 $K$ 限制）”是安全的：携带数越大，只会让后续更多边满足 $W$，不会使可达性变差（因不可减少携带数）。

2. 二分答案

   • 上界 $R=\sum A_i$（携带数不可能超过总可拿数），下界 $L=0$。
   • 若 check(R) 为假，则无论怎么拿都到不了 $n$，答案为 $-1$。
   • 否则在 $[0,R]$ 二分，找最小可行的 $K$。

正确性要点

• 单调性：可行集合对 $K$ 单调不减，支持二分。
• 最优子结构/贪心安全：在固定 $K$ 下，局部把携带数尽量做大只会放宽后续边的限制。
• 拓扑顺序：由 $u < v$ 可直接按编号顺序做一次 DP。

复杂度分析

• 每次 check(K)：遍历所有点和边，时间 $O(n+m)$，空间 $O(n+m)$。
• 二分次数约 $\log_2(\sum A_i)$（$\sum A_i \le 10^{14}$ 量级，约 47 次）。
• 总时间复杂度：$O\big((n+m)\log(\sum A_i)\big)$，空间复杂度：$O(n+m)$。

代码实现

Python 实现

import sys

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    A = [0] * (n + 1)
    for i in range(1, n + 1):
        A[i] = int(next(it))

    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        g[u].append((v, w))  # 单向边 u->v, 需求 w

    # 可行性检查：是否存在从 1 到 n 的路径，使得携带数始终 ≤ K 且满足边需求
    def check(K: int) -> bool:
        NEG = -1
        s = [NEG] * (n + 1)
        # 起点携带 0，最多可在 1 号营地拿 A[1]，但不能超过 K
        s[1] = min(K, A[1])
        for u in range(1, n + 1):
            if s[u] < 0:
                continue
            for v, w in g[u]:
                if s[u] >= w:  # 边需求满足
                    cand = s[u] + A[v]
                    if cand > K:
                        cand = K
                    if cand > s[v]:
                        s[v] = cand
        return s[n] >= 0

    R = sum(A)
    if not check(R):
        print(-1)
        return

    # 二分最小可行 K
    L, ans = 0, R
    while L <= R:
        mid = (L + R) // 2
        if check(mid):
            ans = mid
            R = mid - 1
        else:
            L = mid + 1
    print(ans)

if __name__ == "__main__":
    main()

Java 实现

import java.util.*;

public class Main {

    static class Edge {
        int v;
        long w;
        Edge(int v, long w) { this.v = v; this.w = w; }
    }

    static int n, m;
    static long[] A;
    static ArrayList<Edge>[] g;

    // 可行性检查：是否存在路径，在上限 K 下能到达 n
    static boolean check(long K) {
        long NEG = -1;
        long[] s = new long[n + 1];
        Arrays.fill(s, NEG);
        // 起点携带 0，可在 1 号营地拿 A1，但不超过 K
        s[1] = Math.min(K, A[1]);

        // 由于保证 u < v，按编号顺序即拓扑顺序遍历
        for (int u = 1; u <= n; u++) {
            if (s[u] < 0) continue; // 不可达
            for (Edge e : g[u]) {
                if (s[u] >= e.w) { // 满足边需求
                    int v = e.v;
                    long cand = s[u] + A[v]; // 到达 v 后再拿 Av
                    if (cand > K) cand = K;  // 不超过上限 K
                    if (cand > s[v]) s[v] = cand; // 取能达到的最大值
                }
            }
        }
        return s[n] >= 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        A = new long[n + 1];
        for (int i = 1; i <= n; i++) A[i] = sc.nextLong();

        g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            long w = sc.nextLong();
            g[u].add(new Edge(v, w));
        }

        // 上界为所有 A 之和
        long R = 0;
        for (int i = 1; i <= n; i++) R += A[i];

        // 若在最大上限下仍不可达，则无解
        if (!check(R)) {
            System.out.println(-1);
            return;
        }

        // 二分最小可行 K
        long L = 0, ans = R;
        while (L <= R) {
            long mid = (L + R) >>> 1;
            if (check(mid)) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

C++ 实现

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

using int64 = long long;

struct Edge {
    int v;
    long long w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> A(n + 1);
    for (int i = 1; i <= n; ++i) cin >> A[i];

    vector<vector<Edge>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    auto check = [&](long long K) -> bool {
        const long long NEG = -1;
        vector<long long> s(n + 1, NEG);
        s[1] = min(K, A[1]); // 起点可拿 A1，但不超过 K
        for (int u = 1; u <= n; ++u) {
            if (s[u] < 0) continue;
            for (auto &e : g[u]) {
                if (s[u] >= e.w) {
                    int v = e.v;
                    long long cand = s[u] + A[v];
                    if (cand > K) cand = K;
                    if (cand > s[v]) s[v] = cand;
                }
            }
        }
        return s[n] >= 0;
    };

    long long R = 0;
    for (int i = 1; i <= n; ++i) R += A[i];

    if (!check(R)) {
        cout << -1 << '\n';
        return 0;
    }

    long long L = 0, ans = R;
    while (L <= R) {
        long long mid = (L + R) >> 1;
        if (check(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

题目内容

多多最近迷上了登山挑战，准备完成一次从山脚(第 $1$ 座营地)出发、最终抵达山顶(第 $n$ 座营地)的攀登路线。

多多本次要挑战的山峰一共有 $n$ 座营地，编号为 $1$ 到 $n$ 。第 $i$ 座营地提供 $Ai$ 个“补给包”，离开营地 $i$ 时，多多可以选择额外带走不超过 $Ai$ 个、任意数量 的补给包，但不能放下已经携带的补给包。多多每次抵达一个营地时，所有之前带上的补给包都会被重新补满。

一共有 $m$ 条单向路线连接着这些营地，第 $i$ 条路线连接从营地 $Ui$ 到 $Vi$ 的路(保证 $Ui<Vi$ )，多多想要通过第 $i$ 条路线，必须随身携带至少 $Wi$ 个补给包，否则中途会因资源不足而放弃。

初始时，多多在第 $1$ 座营地，手中没有任何补给包。目标是抵达第 $n$ 座营地，完成本次登山挑战。请你帮多多规划路线，使得在成功抵达终点时，多多携带的补给包数量最少。

输入描述

第一行包括两个整数，营地数 $n$ 和路线数 $m(2≤n≤1×10^5,0≤m≤5×10^5)$。

第二行包括 $n$ 个整数 $A_1,A_2,...,A_n(0 ≤ Ai≤ 10^9)$ ，表示每个营地可获取的补给包数量。

接下来 $m$ 行，每行包含三个整数 $Ui,Vi,Wi (1≤ Ui<Vi≤n,1≤Wi≤10^9)$ ,表示从营地 $Ui$ 到 $Vi$ 的单向路线最少需要携带 $Wi$ 个补给包。

输出描述

输出成功抵达终点时多多携带的最少补给包数量。

若无法抵达第 $n$ 座营地，请输出 $-1$ 。

样例1

输入

5 6
2 5 2 0 1
1 2 1
2 5 5
1 3 2
3 4 4
1 4 3
4 5 3

输出

4

说明

在营地 $1$ 带走 $2$ 个补给包，移动到营地 $3$ ；在营地 $3$ 带走 $2$ 个补给包，移动到营地 $4$ ；在营地 $4$ 补充完毕，移动到营地 $5$ ，抵达终点。

*营地 $1$ 只有 $2$ 个补给包，无法直接移动到营地 $4$ 。