結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2017-06-16 00:07:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 850 bytes |
コンパイル時間 | 511 ms |
コンパイル使用メモリ | 68,096 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:31:09 |
合計ジャッジ時間 | 1,596 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <algorithm> using namespace std; int main(){ int n, c, v; cin >> n >> c >> v; int s[v], t[v], y[v], m[v]; for(int i = 0; i < v; i++) cin >> s[i]; for(int i = 0; i < v; i++) cin >> t[i]; for(int i = 0; i < v; i++) cin >> y[i]; for(int i = 0; i < v; i++) cin >> m[i]; int dp[n + 1][c + 1]; //dp[i][j] := 町iにいて、j円使った時に掛かる時間 fill(dp[0], dp[n + 1], 1e9); for(int i = 0; i < c + 1; i++) dp[1][i] = 0; bool update = true; while(update){ update = false; for(int i = 0; i < v; i++) for(int j = 0; j < c + 1; j++) if(0 <= j - y[i] && j - y[i] < c + 1 && dp[s[i]][j - y[i]] + m[i] < dp[t[i]][j]){ dp[t[i]][j] = dp[s[i]][j - y[i]] + m[i]; update = true; } } int ans = 1e9; for(int i = 0; i < c + 1; i++) ans = min(ans, dp[n][i]); cout << (ans == 1e9 ? -1 : ans) << endl; }