結果

問題 No.20 砂漠のオアシス
ユーザー mudbdbmudbdb
提出日時 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));
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0