結果

問題 No.3111 Toll Optimization
ユーザー Hoang Nho Dinh
提出日時 2025-04-19 00:51:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 117 ms / 5,000 ms
コード長 1,202 bytes
コンパイル時間 1,980 ms
コンパイル使用メモリ 202,576 KB
実行使用メモリ 13,360 KB
最終ジャッジ日時 2025-04-19 00:51:23
合計ジャッジ時間 7,376 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
const int nxm = 1e5 + 10;
int n, m, numCoupons;
vector<pair<int, int>> g[nxm];
int c[nxm];
long long dist[nxm][4];

void dijkstra(int k) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	pq.push({0, 1});
	dist[1][0] = 0;
	while (!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();
		if (dist[u][k] < d) continue;
		for (auto [v, w] : g[u]) {
			long long keep = d + w;
			long long use = k > 0 ? dist[u][k - 1] : 1e18;
			long long newCost = min(keep, use);	
			if (dist[v][k] > newCost) {
				dist[v][k] = newCost;
				pq.push({newCost, v});
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> numCoupons;
	for (int i = 1; i <= m; i++)
		cin >> c[i];
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, c[i]});
		g[v].push_back({u, c[i]});
	}
	memset(dist, 0x3f, sizeof dist);
	for (int i = 0; i <= numCoupons; i++) {
		dijkstra(i);
	}
	long long ans = 1e14;
	for (int i = 0; i <= numCoupons; i++) {
		ans = min(ans, dist[n][i]);
	}
	if (ans >= 1e14) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}
	return 0;
}
0