結果
問題 | No.20 砂漠のオアシス |
ユーザー | mudbdb |
提出日時 | 2015-07-16 22:46:46 |
言語 | C90 (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 95 ms / 5,000 ms |
コード長 | 3,966 bytes |
コンパイル時間 | 564 ms |
コンパイル使用メモリ | 23,296 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 05:20:32 |
合計ジャッジ時間 | 1,712 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:170:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 170 | scanf("%d", &N); | ^~~~~~~~~~~~~~~ main.c:171:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 171 | scanf("%d", &V); | ^~~~~~~~~~~~~~~ main.c:172:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 172 | scanf("%d", &Ox); | ^~~~~~~~~~~~~~~~ main.c:173:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 173 | scanf("%d", &Oy); | ^~~~~~~~~~~~~~~~ main.c:182:7: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 182 | scanf("%d", &(Q[i][j].L)); | ^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h>#include <stdlib.h>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; i<N; i++) {for (j=0; j<N; j++) {Q[i][j].x = i;Q[i][j].y = j;Q[i][j].next = 0;Q[i][j].prev = 0;Q[i][j].d = ~(1 << 31);Q[i][j].flag = 0;}}Q[startx][starty].d = 0;list_in(&(Q[startx][starty]));struct vertex *u;struct vertex *v;for (u=list_out(); u!=0; u=list_out()) {for (v=side_init(u,Q,N); v!=0; v=side()) {if (v->d > 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<N; i++) Q[i] = &(Q[i-1][N]);for (j=0; j<N; j++) {for (i=0; i<N; i++) {scanf("%d", &(Q[i][j].L));}}char *ans;char *YES = "YES";char *NO = "NO";dijkstra(0, 0, Q, N);if (V > 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;}