結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2017-10-04 22:09:43 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 984 bytes |
コンパイル時間 | 1,311 ms |
コンパイル使用メモリ | 161,888 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:33:31 |
合計ジャッジ時間 | 2,554 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF 100000000 using P = pair<int, int>; int N, C, V; int S[1500], T[1500], Y[1500], M[1500]; int dp[300][50]; vector<P> r[50][50]; int recursive(int y, int p) { if(y < 0) return INF; if(dp[y][p] > 0) return dp[y][p]; if(p == N - 1) return 0; int L = INF; for(int i = 0; i < N; i++) { if(i == p) continue; vector<P> *v = &r[p][i]; for(auto it = v->begin(); it != v->end(); it++) { L = min(recursive(y - it->first, i) + it->second, L); } } dp[y][p] = L; return L; } int main() { cin >> N >> C >> 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]; S[i]--, T[i]--; r[S[i]][T[i]].push_back(P(Y[i], M[i])); } for(int i = 0; i < C; i++) { for(int j = 0; j < N; j++) { dp[i][j] = -1; } } dp[C][0] = 0; int L = recursive(C, 0); if(L >= INF) L = -1; cout << L << endl; return 0; }