結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー みどりむし🦠
提出日時 2025-04-19 09:06:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 364 ms / 5,000 ms
コード長 1,077 bytes
コンパイル時間 4,187 ms
コンパイル使用メモリ 295,692 KB
実行使用メモリ 19,760 KB
最終ジャッジ日時 2025-04-19 09:06:33
合計ジャッジ時間 16,323 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

constexpr long INF64 = 1L << 60;

int main() {
	int n, m, k; std::cin >> n >> m >> k;
	std::vector<long> c(m); for(auto&& x : c) std::cin >> x;
	std::vector<std::vector<std::pair<int, long>>> g(n);
	for(int i : std::views::iota(0, m)) {
		int u, v; std::cin >> u >> v; --u, --v;
		g[u].emplace_back(v, c[i]);
		g[v].emplace_back(u, c[i]);
	}

	std::priority_queue<std::tuple<long, int, int>, std::vector<std::tuple<long, int, int>>, std::greater<>> que;
	que.emplace(0, 0, 0);
	
	std::vector dist(n, std::vector(k + 1, INF64));
	dist[0][0] = 0;
	
	while(!que.empty()) {
		auto [ d, v, z ] = que.top(); que.pop();
		
		if(d > dist[v][z]) continue;
		
		for(int dz : std::views::iota(0, 2)) {
			auto nz = z + dz;
			if(nz > k) continue;

			for(auto e : g[v]) {
				auto nv = e.first;
				auto nd = dz == 0 ? d + e.second : d;

				if(nd >= dist[nv][nz]) continue;
				dist[nv][nz] = nd;
				que.emplace(nd, nv, nz);
			}
		}
	}
	
	auto ans = std::ranges::min(dist[n-1]);
	if(ans >= INF64) std::cout << -1;
	else std::cout << ans;
	std::cout << "\n";
}
0