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

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_g

前提知識

• ダイクストラ

解説

https://atcoder.jp/contests/iroha2019-day2/submissions/5215078

ダイクストラをやる。
(到達している駅, 手にしている花)を状態として、コストは使ったお金である。
注意すべきこと

• 花をK本以上買ったとしても、全てK本として丸める
• 花のセットを何本も買えるとしても、1セットだけ買う遷移のみ書く

2番目の注意だが、
例えば3本の花のセットが買える駅4にいて、2本の花を持っているとする。
すると、(4, 2)からの遷移として、(4, 5), (4, 8), (4, 11), ...とたくさんあるが、(4, 2)から(4,5)の遷移だけをする。
これで問題無い理由は、(4,5)から(4,8)の遷移があり、かつ、経由した遷移でも一気に遷移するのと結果は変わらないためである。
このように遷移がたくさんある場合に、隣接する遷移だけに絞ることで遷移を減らすテクはよく使う。

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[1010][1010];
ll dp[1010][1010];
int N, M, K;
int X[1010], Y[1010];
vector<pair<int, int>> E[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> K;
	rep(i, 0, M) {
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		E[a].push_back({ b, c });
		E[b].push_back({ a, c });
	}
	rep(i, 0, N) cin >> X[i] >> Y[i];
 
	rep(i, 0, N + 1) rep(k, 0, K + 1) dp[i][k] = infl;
	
	min_priority_queue<pair<ll, int>> que;
 
	dp[0][0] = 0;
	que.push({ 0, 0 });
 
	while (!que.empty()) {
		auto q = que.top(); que.pop();
 
		ll cst = q.first;
		int cu = q.second % 1010;
		int k = q.second / 1010;
 
		if (vis[cu][k]) continue;
		vis[cu][k] = 1;
 
		fore(p, E[cu]) {
			ll cst2 = cst + p.second;
			int to = p.first;
 
			if (vis[to][k]) continue;
			if (chmin(dp[to][k], cst2)) que.push({ dp[to][k], k * 1010 + to });
		}
 
		if (k < K) {
			int kk = min(K, k + X[cu]);
			ll cst2 = cst + Y[cu];
			if (vis[cu][kk]) continue;
			if (chmin(dp[cu][kk], cst2)) que.push({ dp[cu][kk], kk * 1010 + cu });
		}
	}
 
	if (dp[N-1][K] == infl) dp[N-1][K] = -1;
	cout << dp[N-1][K] << endl;
}