結果

問題 No.20 砂漠のオアシス
ユーザー mudbdbmudbdb
提出日時 2015-07-16 22:46:46
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 90 ms / 5,000 ms
コード長 3,966 bytes
コンパイル時間 916 ms
コンパイル使用メモリ 23,552 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-21 06:38:27
合計ジャッジ時間 1,802 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 0 ms
5,376 KB
testcase_02 AC 0 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 70 ms
5,376 KB
testcase_06 AC 82 ms
5,376 KB
testcase_07 AC 88 ms
5,376 KB
testcase_08 AC 42 ms
5,376 KB
testcase_09 AC 90 ms
5,376 KB
testcase_10 AC 0 ms
5,376 KB
testcase_11 AC 0 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 4 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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));
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#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;
}
0