結果

問題 No.1449 新プロランド
コンテスト
ユーザー Hydrogen332
提出日時 2025-11-16 00:02:03
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 1,298 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,674 ms
コンパイル使用メモリ 293,348 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-16 00:02:09
合計ジャッジ時間 4,312 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, e) for (int i = (int)(s); i < (int)(e); ++i)

template<typename T>
bool chmin(T &a, T b) {
	return ((a > b) ? (a = b, true) : (false));
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	
	int N, M;
	cin >> N >> M;
	vector<vector<pair<int, int>>> G(N);
	rep(i, 0, M) {
		int A, B, C;
		cin >> A >> B >> C;
		--A, --B;
		G[A].push_back({B, C});
		G[B].push_back({A, C});
	}
	vector<int> T(N);
	rep(i, 0, N) cin >> T[i];
	
	const ll INF = 1ll << 60;
	
	int maxiC = 1010;
	vector dist(N, vector<ll>(maxiC + 1, INF));
	priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> que;
	dist[0][T[0]] = T[0];
	que.push({T[0], {0, T[0]}});
	
	while (!que.empty()) {
		ll d = que.top().first;
		int v = que.top().second.first;
		int p = que.top().second.second;
		que.pop();
		
		if (d > dist[v][p]) continue;
		
		for (pair<int, int> e : G[v]) {
			if (chmin(dist[e.first][min(maxiC, p + T[e.first])], dist[v][p] + e.second / p + T[e.first])) {
				que.push({dist[e.first][min(maxiC, p + T[e.first])], {e.first, min(maxiC, p + T[e.first])}});
			}
		}
	}
	
	ll ans = INF;
	rep(i, 0, maxiC + 1) ans = min(ans, dist[N - 1][i]);
	cout << ans << '\n';
}
0