結果

問題 No.3111 Toll Optimization
ユーザー siro53
提出日時 2025-04-19 18:04:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 357 ms / 5,000 ms
コード長 998 bytes
コンパイル時間 3,802 ms
コンパイル使用メモリ 294,420 KB
実行使用メモリ 19,760 KB
最終ジャッジ日時 2025-04-19 18:04:20
合計ジャッジ時間 16,031 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll LLINF = 1LL << 60;

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	vector<ll> C(M);
	for(auto& e : C) cin >> e;
	vector<vector<pair<int, ll>>> G(N);
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		G[u].emplace_back(v, C[i]);
		G[v].emplace_back(u, C[i]);
	}
	vector<vector<ll>> dp(N, vector<ll>(K + 1, LLINF));
	using Data = tuple<ll, int, int>;
	priority_queue<Data, vector<Data>, greater<Data>> que;
	que.emplace(0, 0, K);
	dp[0][K] = 0;
	while(!que.empty()) {
		auto [d, u, rem] = que.top();
		que.pop();
		if(dp[u][rem] < d) continue;
		for(auto [v, w] : G[u]) {
			if(dp[v][rem] > d + w) {
				dp[v][rem] = d + w;
				que.emplace(dp[v][rem], v, rem);
			}
			if(rem > 0 and dp[v][rem - 1] > d) {
				dp[v][rem - 1] = d;
				que.emplace(dp[v][rem - 1], v, rem - 1);
			}
		}
	}
	ll ans = *min_element(dp[N - 1].begin(), dp[N - 1].end());
	if(ans == LLINF) ans = -1;
	cout << ans << endl;
}
0