CF-1026-D. Fewer Batteries

思路讲解

检查点之间共有 $m$ 条单向通道。第 $i$ 条通道允许从点 $s_i$ 移动到点 $t_i$（$s_i < t_i$），但不允许反方向移动。此外，只有当机器人至少拥有 $w_i$ 个充电电池时，才能使用第 $i$ 条通道；否则，它将在途中耗尽电量。

这个 $s_i < t_i$ 尤为关键，这说明了这张图是有向无环图（DAG）。

那么二分做法不用多说，使用天然的拓扑排序以及类似dp做法解决，然后注意斜体加粗部分。

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

源代码

// 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，该代码一个点被访问多次，那么其所有边都将重新遍历一次。

源代码

// 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;
}
/*

*/