#include #include #include #include #include #include using namespace std; #define MAX_VAL 10101010 int N,C,V; int memo[51][301]; int map[2][51][51]; int ret; int recursive(int cur_node, int cur_cost) { int min_dist = MAX_VAL; if (memo[cur_node][cur_cost] != MAX_VAL) return memo[cur_node][cur_cost]; if (cur_node == N) return 0; for (int n = 1; n <= N; n++) { if (map[0][cur_node][n] == -1) continue; if ((cur_cost+map[1][cur_node][n]) > C) continue; int min_dist_tmp = recursive(n, cur_cost+map[1][cur_node][n])+map[0][cur_node][n]; min_dist = min(min_dist, min_dist_tmp); } // cout << "cur_node = " << cur_node << " cur_cost = " << cur_cost << " min_dist = " << min_dist << endl; memo[cur_node][cur_cost] = min_dist; return min_dist; } int main() { cin >> N >> C >> V; vector S(V); vector T(V); vector Y(V); vector 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]; for (int n = 0; n <= N; n++) for (int c = 0; c <= C; c++) { memo[n][c] = MAX_VAL; } for (int k = 0; k < 2; k++) for (int j = 0; j < 51; j++) for (int i = 0; i < 51; i++) map[k][j][i] = -1; for (int i = 0; i < V; i++) { map[0][S[i]][T[i]] = M[i]; map[1][S[i]][T[i]] = Y[i]; } // for (int c = 0; c <= C; c++) dp[1][c] = 0; int ret = recursive(1, 0); if (ret == MAX_VAL) ret = -1; cout << ret << endl; // for (int n_f = 1; n_f <= N; n_f++) // int ret = MAX_VAL; // for (int c = 0; c <= C; c++) { // ret = min(ret,memo[N][c]); // } // cout << ret << endl; // for (int k = 1; k <= N; k++) // for (int j = 1; j <= N; j++) // for (int i = 1; i <= N; i++) { // if (dp[0][i][j]