#include #include struct vertex { struct vertex *next; struct vertex *prev; int d; int L; int flag; short int x; short int y; }; struct vertex *Root = 0; void list_in(struct vertex *in) { if (in->flag == 0) { if (in->next != 0) { if (in->prev != 0) { if ((in->prev->d <= in->d) && (in->d <= in->next->d)) { goto END; } in->prev->next = in->next; in->next->prev = in->prev; } else { if (in->d <= in->next->d) { goto END; } in->next->prev = 0; Root = in->next; } } else { if (in->prev != 0) { if (in->prev->d <= in->d) { goto END; } in->prev->next = 0; } else { if (Root == 0) { Root = in; goto END; } else if (Root == in) { goto END; } else { // } } } struct vertex *cur; struct vertex *hold = 0; for (cur=Root; cur!=0; cur=cur->next) { if (in->d <= cur->d) { break; } else { hold = cur; } } if (cur == 0) { if (hold != 0) { hold->next = in; in->prev = hold; in->next = 0; } else { in->prev = 0; in->next = 0; Root = in; } } else { if (cur->prev != 0) { cur->prev->next = in; in->prev = cur->prev; in->next = cur; cur->prev = in; } else { in->prev = 0; in->next = cur; cur->prev = in; Root = in; } } } END: ; return; } struct vertex *list_out() { struct vertex *out; if (Root != 0) { out = Root; if (out->next != 0) { out->next->prev = 0; Root = out->next; out->next = 0; } else { Root = 0; } out->flag = 1; } else { out = 0; } return out; } int List_n = 0; struct vertex *List[4]; struct vertex *side_init(struct vertex *u, struct vertex **Q, int N) { List_n = 0; if (0 <= u->x-1) { List[List_n] = &(Q[u->x-1][u->y]); List_n++; } if (u->x+1 < N) { List[List_n] = &(Q[u->x+1][u->y]); List_n++; } if (0 <= u->y-1) { List[List_n] = &(Q[u->x][u->y-1]); List_n++; } if (u->y+1 < N) { List[List_n] = &(Q[u->x][u->y+1]); List_n++; } List_n--; return List[List_n]; } struct vertex *side(void) { if (List_n >= 1) { List_n--; return List[List_n]; } else { return 0; } } void dijkstra(int startx, int starty, struct vertex **Q, int N) { int i; int j; for (i=0; id > u->d + v->L) { v->d = u->d + v->L; list_in(v); } } } return; } int main() { int N; int V; int Ox; int Oy; scanf("%d", &N); scanf("%d", &V); scanf("%d", &Ox); scanf("%d", &Oy); int i; int j; struct vertex **Q; Q = (struct vertex**)malloc(sizeof(struct vertex*)*N); Q[0] = (struct vertex*)malloc(sizeof(struct vertex)*N*N); for (i=1; i Q[N-1][N-1].d) { ans = YES; } else { if ((Ox == 0) || (Oy == 0)) { ans = NO; } else { V = (V - Q[Ox-1][Oy-1].d)*2; if (V > 0) { dijkstra(Ox-1, Oy-1, Q, N); if (V > Q[N-1][N-1].d) { ans = YES; } else { ans = NO; } } else { ans = NO; } } } printf("%s\n", ans); return 0; }