結果
問題 | No.20 砂漠のオアシス |
ユーザー | scache |
提出日時 | 2014-11-12 03:48:28 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,257 bytes |
コンパイル時間 | 3,478 ms |
コンパイル使用メモリ | 78,496 KB |
実行使用メモリ | 54,600 KB |
最終ジャッジ日時 | 2024-04-21 06:18:26 |
合計ジャッジ時間 | 9,924 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 121 ms
41,044 KB |
testcase_01 | AC | 126 ms
41,372 KB |
testcase_02 | AC | 131 ms
41,548 KB |
testcase_03 | AC | 204 ms
44,500 KB |
testcase_04 | AC | 215 ms
44,240 KB |
testcase_05 | AC | 422 ms
48,712 KB |
testcase_06 | AC | 378 ms
48,772 KB |
testcase_07 | WA | - |
testcase_08 | AC | 341 ms
47,232 KB |
testcase_09 | AC | 367 ms
48,592 KB |
testcase_10 | WA | - |
testcase_11 | AC | 118 ms
40,896 KB |
testcase_12 | AC | 186 ms
43,024 KB |
testcase_13 | AC | 194 ms
43,340 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 211 ms
45,896 KB |
testcase_18 | WA | - |
testcase_19 | AC | 217 ms
46,480 KB |
testcase_20 | WA | - |
ソースコード
import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; /** * yukicoder no.20 * @author scache * */ public class prog { public static void main(String[] args) { prog p = new prog(); } public prog() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v = sc.nextInt(); int ox = sc.nextInt()-1; int oy = sc.nextInt()-1; Point[][] map = new Point[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ map[i][j] = new Point(i,j,sc.nextInt()); } } solve(v, ox, oy, map); } public void solve(int v, int ox, int oy, Point[][] map) { int distance = dijstra(map, 0, 0, map.length-1, map.length-1); if(v>distance){ System.out.println("YES"); return; } if(ox<0 && oy<0){ System.out.println("NO"); return; } int oDistance = dijstra(map, 0, 0, ox, oy); int gDistance = dijstra(map, ox, oy, map.length-1, map.length-1); if( (v-oDistance)*2>gDistance){ System.out.println("YES"); return; } System.out.println("NO"); } int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; private int dijstra(Point[][] map, int sx, int sy, int tx, int ty){ PriorityQueue<Point> queue = new PriorityQueue<Point>(); int[][] distances = new int[map.length][map.length]; for(int i=0;i<distances.length;i++) Arrays.fill(distances[i], Integer.MAX_VALUE); distances[sx][sy] = 0; queue.offer(map[sx][sy]); while(!queue.isEmpty()){ Point p = queue.poll(); int d = p.d; if(distances[p.x][p.y]<p.d) continue; for(int i=0;i<4;i++){ int nx = p.x+dx[i]; int ny = p.y+dy[i]; if(0<=nx && nx<map.length && 0<=ny && ny<map.length){ if(distances[nx][ny] > distances[p.x][p.y] + map[nx][ny].d){ distances[nx][ny] = distances[p.x][p.y] + map[nx][ny].d; queue.offer(map[nx][ny]); } } } } return distances[tx][ty]; } private class Point implements Comparable<Point>{ public int x; public int y; public int d; public Point(int x, int y, int d){ this.x = x; this.y = y; this.d = d; } @Override public int compareTo(Point arg0) { return d-arg0.d; } } }