#include #include #define True 1 typedef struct state { int position; int Y_sum; int M_sum; } state_t; int main(void) { int N; //街の数 scanf("%d", &N); int C; //手持ちのお金 scanf("%d", &C); int V; //道の数 scanf("%d", &V); int *S; //S街から S = malloc(V * sizeof(int)); for (int i = 0; i < V; i++) { scanf("%d", &S[i]); } int *T; //T街までの移動 T = malloc(V * sizeof(int)); for (int i = 0; i < V; i++) { scanf("%d", &T[i]); } int *Y; //コスト Y = malloc(V * sizeof(int)); for (int i = 0; i < V; i++) { scanf("%d", &Y[i]); } int *M; //時間 M = malloc(V * sizeof(int)); for (int i = 0; i < V; i++) { scanf("%d", &M[i]); } int min_time = 1000 * 1500 + 1; //No.1の道がかかる時間 state_t *current_state; current_state = malloc(V * sizeof(state_t)); state_t *next_state; next_state = malloc(V * sizeof(state_t)); int current_num = 1; int next_num; current_state[0].position = 1; current_state[0].Y_sum = 0; current_state[0].M_sum = 0; int next_Y; int next_M; while (True) { next_num = 0; for (int i = 0; i < current_num; i++) { for (int j = 0; j < V; j++) { if (current_state[i].position == S[j]) { next_Y = current_state[i].Y_sum + Y[j]; next_M = current_state[i].M_sum + M[j]; if (T[j] != N && next_Y <= C) { next_state[next_num].position = T[j]; next_state[next_num].Y_sum = next_Y; next_state[next_num].M_sum = next_M; next_num++; } else if (next_Y <= C) { if (next_M < min_time) { min_time = next_M; } } } } } if (next_num == 0) { break; } for (int i = 0; i < next_num; i++) { current_state[i].position = next_state[i].position; current_state[i].Y_sum = next_state[i].Y_sum; current_state[i].M_sum = next_state[i].M_sum; } current_num = next_num; } if (min_time == 1000 * 1500 + 1) { printf("-1\n"); } else { printf("%d\n", min_time); } }