結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-10-29 22:03:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 919 bytes |
コンパイル時間 | 2,356 ms |
コンパイル使用メモリ | 158,724 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:05:46 |
合計ジャッジ時間 | 2,525 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long int64; int main(){ int N, C, V, S[1500], T[1500], Y[1500], M[1500], dp[50][301]; cin >> N; cin >> C; cin >> V; for(int i = 0; i < V; i++){ cin >> S[i]; S[i]--; } for(int i = 0; i < V; i++){ cin >> T[i]; T[i]--; } for(int i = 0; i < V; i++){ cin >> Y[i]; } for(int i = 0; i < V; i++){ cin >> M[i]; } const int INF = 1 << 30; fill_n( *dp, 50 * 301, INF); dp[0][C] = 0; for(int i = 0; i < N; i++){ for(int j = 0; j <= C; j++){ if(dp[i][j] == INF) continue; for(int k = 0; k < V; k++){ if(S[k] == i && j - Y[k] >= 0){ dp[T[k]][j - Y[k]] = min( dp[T[k]][j - Y[k]], dp[i][j] + M[k]); } } } } int ret = *min_element( dp[N - 1], dp[N]); if(ret != INF) cout << ret << endl; else cout << -1 << endl; }