Codeforces #857 : Div1 D. The way home

これも1750ptで普段より易しめなのね。
https://codeforces.com/contest/1801/problem/D

問題

コスト付きの有向辺を持つN点M辺のグラフが与えられる。
辺に沿って移動する際は、所持金がコスト以上でなければならず、移動するとコスト分所持金が減る。

各点vでパフォーマンスをすると、所持金がW[v]だけ増えるとする。
1番の点からN番の点に至る、最小パフォーマンス回数を求めよ。

解法

f(v,w) := v番の頂点に至る経路で、wは経路中W[w]が最大であるような頂点である場合の、必要パフォーマンス回数の最小値と、その場合の所持金の最大値
とすると、あとは単純にダイクストラ法を回すだけ。
辺に沿って移動するのに所持金が足りない場合、頂点wで必要な分パフォーマンスを行うことにしよう。

int T,N,M,P;
vector<pair<int,int>> E[808];
int W[808],R[808];
vector<int> Ws;
pair<ll,ll> dp[808][808];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>P;
		Ws.clear();
		FOR(i,N) {
			cin>>W[i];
			Ws.push_back(W[i]);
			E[i].clear();
		}
		FOR(i,M) {
			cin>>x>>y>>k;
			E[x-1].push_back({y-1,k});
		}
		
		FOR(i,N) FOR(j,N) dp[i][j]={1LL<<60,0};
		sort(ALL(Ws));
		FOR(i,N) {
			W[i]=lower_bound(ALL(Ws),W[i])-Ws.begin();
		}
		dp[0][W[0]]={0,P};
		
		ll mi=1LL<<60;
		FOR(i,N) {
			int w=Ws[i];
			priority_queue<pair<pair<ll,ll>,int>> Q;
			FOR(j,N) if(dp[j][i].first<(1LL<<60)) {
				Q.push({{-dp[j][i].first,dp[j][i].second},j});
			}
			while(Q.size()) {
				ll num=-Q.top().first.first;
				ll fuel=Q.top().first.second;
				int cur=Q.top().second;
				Q.pop();
				if(dp[cur][i].first!=num||dp[cur][i].second!=fuel) continue;
				if(cur==N-1) mi=min(mi,num);
				FORR2(e,c,E[cur]) {
					int tar=max(i,W[e]);
					
					ll nn=num;
					ll nfuel;
					
					if(fuel>=c) {
						nfuel=fuel-c;
					}
					else {
						ll a=(c-fuel+w-1)/w;
						nn=num+a;
						nfuel=fuel+a*w-c;
					}
					if(dp[e][tar].first>nn||(dp[e][tar].first==nn&&dp[e][tar].second<nfuel)) {
						dp[e][tar]={nn,nfuel};
						if(i==tar) Q.push({{-dp[e][i].first,dp[e][i].second},e});
					}
				}
			}
		}
		
		
		
		if(mi==1LL<<60) mi=-1;
		cout<<mi<<endl;
	}
}

まとめ

D問題の割にだいぶストレート。