結果
問題 | No.20 砂漠のオアシス |
ユーザー | kou6839 |
提出日時 | 2014-11-26 01:13:22 |
言語 | Java19 (openjdk 21) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,999 bytes |
コンパイル時間 | 3,259 ms |
コンパイル使用メモリ | 81,504 KB |
実行使用メモリ | 60,768 KB |
最終ジャッジ日時 | 2023-08-03 07:22:35 |
合計ジャッジ時間 | 9,168 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 113 ms
39,792 KB |
testcase_01 | AC | 120 ms
40,008 KB |
testcase_02 | AC | 120 ms
39,928 KB |
testcase_03 | AC | 183 ms
42,428 KB |
testcase_04 | AC | 194 ms
42,632 KB |
testcase_05 | AC | 376 ms
45,920 KB |
testcase_06 | AC | 403 ms
45,880 KB |
testcase_07 | AC | 380 ms
46,008 KB |
testcase_08 | AC | 419 ms
46,260 KB |
testcase_09 | AC | 380 ms
46,036 KB |
testcase_10 | WA | - |
testcase_11 | AC | 109 ms
39,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 195 ms
42,052 KB |
testcase_14 | AC | 204 ms
43,784 KB |
testcase_15 | AC | 195 ms
42,744 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 251 ms
60,768 KB |
testcase_20 | AC | 188 ms
57,164 KB |
ソースコード
import java.math.BigInteger; import java.util.*; class pair implements Comparable{ int x; int y; int cost; pair(int x,int y,int cost){ this.x=x; this.y=y; this.cost=cost; } @Override public int compareTo(Object o) { // TODO Auto-generated method stub pair aaa=(pair)o; return this.cost-aaa.cost; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] vx ={1,0,-1,0}; int[] vy= {0,1,0,-1}; int n=sc.nextInt(); int hp=sc.nextInt(); int ox=sc.nextInt(); int oy=sc.nextInt(); int[][] edge = new int[n+1][n+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ edge[i][j]=sc.nextInt(); } } PriorityQueue<pair> queue = new PriorityQueue<pair>(); int[][] dp = new int[n+1][n+1]; for(int i=1;i<=n;i++){ Arrays.fill(dp[i], Integer.MAX_VALUE); } dp[1][1]=0; queue.add(new pair(1,1,0)); while(!queue.isEmpty()){ pair temp =queue.poll(); if(dp[temp.x][temp.y]<temp.cost) continue; for(int i=0;i<4;i++){ if(temp.x+vx[i]<1||temp.x+vx[i]>n||temp.y+vy[i]<1||temp.y+vy[i]>n) continue; int costt = edge[temp.x+vx[i]][temp.y+vy[i]]; if(dp[temp.x+vx[i]][temp.y+vy[i]]>dp[temp.x][temp.y]+costt){ dp[temp.x+vx[i]][temp.y+vy[i]]=dp[temp.x][temp.y]+costt; queue.add(new pair(temp.x+vx[i],temp.y+vy[i],dp[temp.x+vx[i]][temp.y+vy[i]])); } } } if(ox!=0&&oy!=0){ int[][] dpp = new int[n+1][n+1]; for(int i=1;i<=n;i++){ Arrays.fill(dpp[i], Integer.MAX_VALUE); } dpp[ox][oy]=0; queue.add(new pair(ox,oy,0)); while(!queue.isEmpty()){ pair temp =queue.poll(); if(dpp[temp.x][temp.y]<temp.cost) continue; for(int i=0;i<4;i++){ if(temp.x+vx[i]<1||temp.x+vx[i]>n||temp.y+vy[i]<1||temp.y+vy[i]>n) continue; int costt = edge[temp.x+vx[i]][temp.y+vy[i]]; if(dpp[temp.x+vx[i]][temp.y+vy[i]]>dpp[temp.x][temp.y]+costt){ dpp[temp.x+vx[i]][temp.y+vy[i]]=dpp[temp.x][temp.y]+costt; queue.add(new pair(temp.x+vx[i],temp.y+vy[i],dpp[temp.x+vx[i]][temp.y+vy[i]])); } } } if(dp[n][n]<hp){ System.out.println("YES"); return; }else{ if( (hp-dp[ox][oy])*2>dpp[n][n]){ System.out.println("YES"); return; } System.out.println("NO"); } } else{ if(dp[n][n]<hp){ System.out.println("YES"); return; }else{ System.out.println("NO"); return; } } } }