AtCoder ABC #164 : E - Two Currencies

EとFの難易度差大きいな。
https://atcoder.jp/contests/abc164/tasks/abc164_e

問題

N頂点M辺の無向連結グラフが与えられる。
各辺について、移動に要する銀貨の枚数と時間が与えられる。
各頂点では、手持ちの金貨を銀貨に両替できる。その際一度の両替で得られる銀貨の枚数とかかる時間が頂点毎に与えられる。

初期状態で1番の頂点におり、銀貨の枚数がSだとする。
各頂点に至る最短時間を求めよ。

解法

頂点数Nと、辺の移動にかかる銀貨の枚数の上限max(A)が小さいことに留意しよう。
銀貨はO(N*max(A))以上持つ必要がない。
そこで以下を考え、ダイクストラ法で最短経路を求めればよい。
f(v,n) := 頂点v・銀貨所持数nに至る最短時間

int N,M;
vector<vector<int>> E[51];
int S;
int D[50],C[50];
ll dp[51][2525];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	S=min(2500,S);
	FOR(i,M) {
		cin>>x>>y>>j>>r;
		E[x-1].push_back({y-1,j,r});
		E[y-1].push_back({x-1,j,r});
	}
	FOR(i,N) cin>>C[i]>>D[i];
	
	FOR(i,N) FOR(x,2501) dp[i][x]=1LL<<60;
	dp[0][S]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,S});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second/10000;
		int S=Q.top().second%10000;
		Q.pop();
		if(co!=dp[cur][S]) continue;
		
		if(S<2500) {
			if(dp[cur][min(2500,S+C[cur])]>co+D[cur]) {
				dp[cur][min(2500,S+C[cur])]=co+D[cur];
				Q.push({-dp[cur][min(2500,S+C[cur])], cur*10000+min(2500,S+C[cur])});
			}
		}
		FORR(e,E[cur]) if(S>=e[1]) {
			if(dp[e[0]][S-e[1]]>co+e[2]) {
				dp[e[0]][S-e[1]]=co+e[2];
				Q.push({-dp[e[0]][S-e[1]], e[0]*10000+S-e[1]});
			}
		}
	}
	
	for(i=1;i<N;i++) {
		ll mi=1LL<<60;
		FOR(j,2501) mi=min(mi,dp[i][j]);
		cout<<mi<<endl;
	}
	
	
}

まとめ

こちらはすんなり。