// yukicoder: No.1 道のショートカット // 2019.4.7 bal4u // 最短距離に関する問題。ダイクストラ法でやってみる #include #include #include //// 高速入力 #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() // 非負整数の入力 { int n = 0, c = gc(); // while (isspace(c)) c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } //// 優先度付きキュー(ダイクストラ法用) #define MAX 1000000 typedef struct { int t, n, money; } QUE; QUE que[MAX]; int qsize; #define PARENT(i) ((i)>>1) #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1)+1) void min_heapify(int i) { int l, r, min; QUE qt; l = LEFT(i), r = RIGHT(i); if (l < qsize && que[l].t < que[i].t) min = l; else min = i; if (r < qsize && que[r].t < que[min].t) min = r; if (min != i) { qt = que[i]; que[i] = que[min]; que[min] = qt; min_heapify(min); } } void deq() { que[0] = que[--qsize]; min_heapify(0); } void enq(int n, int t, int money) { int i, min; QUE qt; i = qsize++; que[i].t = t, que[i].n = n, que[i].money = money; while (i > 0 && que[min = PARENT(i)].t > que[i].t) { qt = que[i]; que[i] = que[min]; que[min] = qt; i = min; } } // 本問題関連 #define MAXN 55 int C; // 使える金額の上限 int N; // 町数 int V; // 道路の本数 int hi[MAXN], *to[MAXN], *money[MAXN], *tim[MAXN]; char vis[MAXN]; int S[MAXN], T[MAXN], Y[MAXN], M[MAXN]; int dijkstra(int start, int goal) { int i, n, t, m, nx; enq(start, 0, 0); while (qsize) { n = que[0].n, t = que[0].t, m = que[0].money, deq(); if (n == goal) return t; if (vis[n]) continue; vis[n] = 1; for (i = 0; i < hi[n]; i++) { if (m + money[n][i] > C) continue; nx = to[n][i]; if (!vis[nx]) enq(nx, t + tim[n][i], m + money[n][i]); } } return -1; } int main() { int i, k, s; N = in(), C = in(), V = in(); for (i = 0; i < V; i++) S[i] = in(), hi[S[i]]++; for (i = 0; i < V; i++) T[i] = in(); for (i = 0; i < V; i++) Y[i] = in(); for (i = 0; i < V; i++) M[i] = in(); for (i = 1; i <= N; i++) if (hi[i]) { to[i] = malloc(sizeof(int)*hi[i]); money[i] = malloc(sizeof(int)*hi[i]); tim[i] = malloc(sizeof(int)*hi[i]); } memset(hi, 0, sizeof(hi)); for (i = 0; i < V; i++) { s = S[i]; k = hi[s]++; to[s][k] = T[i], money[s][k] = Y[i], tim[s][k] = M[i]; } printf("%d\n", dijkstra(1, N)); return 0; }