いろはちゃんコンテスト Day2 : G - 通学路

これも解法は典型かな。って今回典型がテーマなんだっけ。
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g

問題

N個の駅と線路が無向グラフを成しており、そのグラフが与えられる。
駅同士の移動にはお金がかかり、その金額が与えられる。

途中の駅で、花を買っていきたい。
駅iで花を買うとき、X[i]本セットをY[i]円で買うことができる。
1つの駅で複数セット買うこともできるが、X[i]本単位のセットでなければ買うことができない。

途中、K本以上の花を買いつつ1番からN番の駅に移動する最小金額を求めよ。

解法

現在値と購入済みの花の本数を状態とし、ダイクストラ法を行うだけ。

int N,M,K;
vector<pair<int,int>> E[2020];
int X[1010];
int Y[1010];


ll dist[1010][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[x-1].push_back({y-1,j});
		E[y-1].push_back({x-1,j});
	}
	FOR(i,N) cin>>X[i]>>Y[i];
	
	FOR(x,1010) FOR(y,2020) dist[x][y]=1LL<<60;
	dist[0][0]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second/2020;
		int num=Q.top().second%2020;
		
		Q.pop();
		if(dist[cur][num]!=co) continue;
		
		// flo
		if(dist[cur][min(num+X[cur],K)]>co+Y[cur]) {
			dist[cur][min(num+X[cur],K)]=co+Y[cur];
			Q.push({-(co+Y[cur]),cur*2020+min(num+X[cur],K)});
		}
		FORR(e,E[cur]) {
			if(dist[e.first][num]>co+e.second) {
				dist[e.first][num]=co+e.second;
				Q.push({-(co+e.second),e.first*2020+num});
			}
		}
	}
	
	if(dist[N-1][K]==1LL<<60) dist[N-1][K]=-1;
	
	cout<<dist[N-1][K]<<endl;
}

まとめ

言われてみると確かに典型か。