結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー sig_256
提出日時 2025-04-20 00:22:03
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 192 ms / 5,000 ms
コード長 1,110 bytes
コンパイル時間 4,355 ms
コンパイル使用メモリ 97,236 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2025-04-20 00:22:19
合計ジャッジ時間 11,312 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>

using P = std::pair<long long, long long>;

std::vector<std::vector<P>> G;

int main(){
	int N, M, K;
	std::cin >> N >> M >> K;
	G.resize(N);
	int C[M];
	for(int & c : C) std::cin >> c;
	for(int m = 0, u, v; m < M; ++m){
		std::cin >> u >> v;
		u--, v--;
		G[u].emplace_back(v, C[m]);
		G[v].emplace_back(u, C[m]);
	}
	std::vector<std::vector<long long>> D(K + 2, std::vector<long long>(N, INT64_MAX));
	for(int k = 0; k <= K; ++k){
		D[k + 1][0] = 0;
		char visited[N];
		std::fill(visited, visited + N, false);
		std::priority_queue<P, std::vector<P>, std::greater<P>> que;
		que.emplace(0, 0);
		do{
			int me = que.top().second;
			que.pop();
			if(visited[me]) continue;
			visited[me] = true;
			for(const auto & p : G[me]){
				long long cost = std::min(D[k][me], D[k + 1][me] + p.second);
				if(cost < D[k + 1][p.first]){
					D[k + 1][p.first] = cost;
					que.emplace(cost, p.first);
				}
			}
		} while(!que.empty());
	}
	if(D[K + 1][N - 1] == INT64_MAX){
		puts("-1");
	}
	else{
		std::cout << D[K + 1][N - 1] << std::endl;
	}
	return 0;
}
0