結果
問題 | No.20 砂漠のオアシス |
ユーザー | リチウム |
提出日時 | 2014-11-16 18:15:34 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,148 bytes |
コンパイル時間 | 2,245 ms |
コンパイル使用メモリ | 80,416 KB |
実行使用メモリ | 58,084 KB |
最終ジャッジ日時 | 2024-04-21 06:19:27 |
合計ジャッジ時間 | 8,823 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 120 ms
41,104 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 211 ms
50,604 KB |
testcase_05 | AC | 489 ms
56,280 KB |
testcase_06 | AC | 524 ms
57,572 KB |
testcase_07 | AC | 538 ms
58,084 KB |
testcase_08 | AC | 534 ms
57,804 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 118 ms
41,324 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 219 ms
45,868 KB |
testcase_15 | AC | 214 ms
46,264 KB |
testcase_16 | AC | 247 ms
47,228 KB |
testcase_17 | WA | - |
testcase_18 | AC | 249 ms
48,388 KB |
testcase_19 | WA | - |
testcase_20 | AC | 181 ms
43,376 KB |
ソースコード
import java.util.*; public class Main { public static int[] dijstra(ArrayList<Integer> e[], ArrayList<Integer> c[], int start) { PriorityQueue<Edge> dij = new PriorityQueue<>(); int ans[] = new int[e.length]; boolean ok[] = new boolean[e.length]; Arrays.fill(ans, Integer.MAX_VALUE); ans[start] = 0; ok[start] = true; dij.add(new Edge(start, 0)); while (!dij.isEmpty()) { Edge ed = dij.poll(); if (ans[ed.p] < ed.c) continue; int a = ed.p; ok[a] = true; for (int i = 0; i < e[a].size(); i++) { int x = e[a].get(i); int y = c[a].get(i); if (!ok[x] && ans[x] > ans[a] + y) { ans[x] = ans[a] + y; dij.add(new Edge(x, ans[x])); } } } return ans; } public static void main(String[] args) { Scanner sc=new Scanner (System.in); int n=sc.nextInt(); int hp=sc.nextInt(); int map[][]=new int[n][n]; int ox=sc.nextInt()-1; int oy=sc.nextInt()-1; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ map[i][j]=sc.nextInt(); } } ArrayList <Integer>e[]=new ArrayList[n*n]; ArrayList <Integer>c[]=new ArrayList[n*n]; for(int i=0;i<n*n;i++){ e[i]=new ArrayList<>(); c[i]=new ArrayList<>(); } for(int i=0;i<n*n;i++){ int x=i/n; int y=i-x*n; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; for(int j=0;j<4;j++){ int nx=x+dx[j]; int ny=y+dy[j]; if(nx<0 || nx>=n || ny<0 || ny>=n)continue; e[i].add(nx*n+ny); c[i].add(map[nx][ny]); } } int dij[]=dijstra(e,c,0); int g=(n-1)*(n-1); if(dij[g]<hp){ System.out.println("YES"); return; } if(ox!=-1){ int oa=ox*n+oy; dij=dijstra(e,c,0); hp-=dij[oa]; hp*=2; dij=dijstra(e,c,oa); if(hp>dij[g]){ System.out.println("YES"); return; } } System.out.println("NO"); } } class Edge implements Comparable<Edge> {//scacheさんから拝借 int p; int c; public Edge(int p, int c) { this.p = p; this.c = c; } public Edge() { } @Override public int compareTo(Edge o) { return this.c - o.c; } }