結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2018-07-06 18:53:37 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,360 bytes |
コンパイル時間 | 507 ms |
コンパイル使用メモリ | 60,920 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:36:23 |
合計ジャッジ時間 | 1,744 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <climits> #include <queue> #include <vector> #define REP(i,a,b) for(int i=(a); i<(b); i++) #define p_int pair<int, int> using namespace std; int main(){ // 街の数、コスト上限、道の数 int city_n, c_max, load_n; cin >> city_n >> c_max >> load_n; // 始点、終点、コスト、時間 int s[load_n], t[load_n], c[load_n], time[load_n]; REP(i, 0, load_n) cin >> s[i]; REP(i, 0, load_n) cin >> t[i]; REP(i, 0, load_n) cin >> c[i]; REP(i, 0, load_n) cin >> time[i]; // 現在地を縦軸、使った費用を横軸に取ってDP int dp[city_n + 1][c_max + 1]; REP(i, 0, city_n + 1){ REP(j, 0, c_max + 1){ dp[i][j] = INT_MAX; } } dp[1][0] = 0; REP(i, 1, city_n) { REP(j, 0, c_max) { if (dp[i][j] == INT_MAX) continue; // i番の都市を始点とする辺を調べる REP(k, 0, load_n){ if (i == s[k] && j + c[k] <= c_max){ dp[t[k]][j + c[k]] = min(dp[t[k]][j + c[k]], dp[i][j] + time[k]); } } } } // dp[city_n][i]における最小値を返す int ans = INT_MAX; REP(i, 0, c_max + 1){ ans = min(ans, dp[city_n][i]); } if (ans == INT_MAX) cout << -1 << endl; else cout << ans << endl; return 0; }