CF-1026-D. Fewer Batteries · znzryb
## 思路讲解
> 检查点之间共有 $m$ 条单向通道。第 $i$ 条通道允许从点 $s_i$ 移动到点 $t_i$（$s_i < t_i$），但不允许反方向移动。此外，只有当机器人至少拥有 $w_i$ 个充电电池时，才能使用第 $i$ 条通道；否则，它将在途中耗尽电量。
这个 $s_i < t_i$ 尤为关键，这说明了这张图是有向无环图（DAG）。
那么二分做法不用多说，使用天然的拓扑排序以及类似dp做法解决，然后注意斜体加粗部分。
```cpp
inline bool check(ll mid){
FOR(i,0,N+5){Mxb[i]=0;}
FOR(i,1,N){
if(i!=1 && Mxb[i]==0) continue;
FOR(j,0,SZ(g[i])-1){
ll v=g[i][j][0],w=g[i][j][1];
if(min(mid,Mxb[i]+B[i])>=w){
Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
Mxb[v]=min(Mxb[v],mid);
}
}
}
if(Mxb[N]==0) return false;
return true;
}
```
## AC代码
[https://codeforces.com/contest/2110/submission/324044393](https://codeforces.com/contest/2110/submission/324044393)
::: 源代码
```cpp
// Problem: D. Fewer Batteries D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,B[MAXN];
vector<arr2> g[MAXN]; // 记得要清空
ll Mxb[MAXN];
// bitset<MAXN> vis;
/*
*/
inline void init(){
FOR(i,0,N+5){g[i].clear();}
}
inline bool check(ll mid){
FOR(i,0,N+5){Mxb[i]=0;}
FOR(i,1,N){
if(i!=1 && Mxb[i]==0) continue;
FOR(j,0,SZ(g[i])-1){
ll v=g[i][j][0],w=g[i][j][1];
// #ifdef LOCAL
// if(w==10){
// debug(Mxb[i]+B[i]);
// }
// #endif
if(min(mid,Mxb[i]+B[i])>=w){
Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
Mxb[v]=min(Mxb[v],mid);
}
// assert(Mxb[i]+B[i]>=w);
}
}
#ifdef LOCAL
debug(mid);
FOR(i,1,N){debug(i);debug(Mxb[i]);}
cerr<<"\n";
#endif
if(Mxb[N]==0) return false;
return true;
}
inline void solve(){
cin>>N>>M;
init();
FOR(i,1,N){
cin>>B[i];
}
ll mxw=0;
FOR(i,1,M){
ll u,v,w;
cin>>u>>v>>w;
// 把g反过来
// g[v].pb({u,w});
g[u].pb({v,w});
mxw=max(mxw,w);
}
ll l=1;ll r=mxw;
if(!check(r)){cout<<-1<<"\n";return;}
while(l<r){
ll mid=l+r>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2110/submission/324044393
*/
```
:::
## 心路历程（WA，TLE，MLE……）
TLE，该代码一个点被访问多次，那么其所有边都将重新遍历一次。
::: 源代码
```cpp
// Problem: D. Fewer Batteries D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,B[MAXN];
vector<arr2> g[MAXN]; // 记得要清空
ll Mx[MAXN];
bitset<MAXN> vis;
/*
*/
inline void init(){
FOR(i,0,N+5){vis[i]=false;Mx[i]=INF;g[i].clear();}
}
void dfs(ll node,ll mx,ll ba){
// vis[node]=true;
#ifdef LOCAL
debug(node);
debug(mx);
debug(ba);
cerr<<"\n";
#endif
Mx[node]=min(Mx[node],mx);
ba+=B[node];
FOR(i,0,SZ(g[node])-1){
ll lnode=g[node][i][0],w=g[node][i][1];
// if(vis[lnode]) continue;
if(ba<w) continue;
dfs(lnode,max(mx,w),ba);
}
}
inline void solve(){
cin>>N>>M;
init();
FOR(i,1,N){
cin>>B[i];
}
FOR(i,1,M){
ll u,v,w;
cin>>u>>v>>w;
// 把g反过来
// g[v].pb({u,w});
g[u].pb({v,w});
}
dfs(1,0,0);
// dfsn(N,0);
if(Mx[N]==INF){ // 未联通
cout<<-1<<"\n";
return;
}
cout<<Mx[N]<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
*/
```
:::