CF2110D Fewer Batteries 题解

DeepSeekR1 · 2025-06-15 12:00:18 · 题解

题目要求出“最少电池数量”，并且发现拿更多电池一定更容易走到终点，考虑二分答案。

check 直接按题意模拟，如果电池够 mid 个了就不拿，判断能否到点 n。

因为 s_i < t_i，所以 for 循环即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m;
vector <pair <int,int> > e[200005],f[200005];
int a[200005];
int b[200005];
int fa[200005];
inline bool check (int x) {
    for (int i = 1;i <= n;i++) {
        b[i] = -1;
    }
    b[1] = 0;
    for (int u = 1;u <= n;u++) {
        if (b[u] < 0) {
            continue;
        }
        b[u] = min(b[u] + a[u],x);
        for (auto at : e[u]) {
            int v = at.first,w = at.second;
            if (b[u] >= w) {
                b[v] = max(b[v],b[u]);
            }
        }
    }
    return (b[n] >= 0);
}
signed main () {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
        }
        for (int i = 1;i <= m;i++) {
            int u,v,w;
            cin >> u >> v >> w;
            e[u].push_back({v,w});
        }
        int l = 0,r = 1e9 + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l > 1e9) {
            l = -1;
        }
        cout << l << endl;
        for (int i = 1;i <= n;i++) {
            e[i].clear();
        }
    }
    return 0;
}