結果
問題 | No.867 避難経路 |
ユーザー | tenten |
提出日時 | 2021-03-04 20:17:07 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 4,637 ms / 6,000 ms |
コード長 | 2,573 bytes |
コンパイル時間 | 2,953 ms |
コンパイル使用メモリ | 80,764 KB |
実行使用メモリ | 151,056 KB |
最終ジャッジ日時 | 2024-04-15 12:27:50 |
合計ジャッジ時間 | 109,133 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 187 ms
43,716 KB |
testcase_01 | AC | 186 ms
43,988 KB |
testcase_02 | AC | 189 ms
43,780 KB |
testcase_03 | AC | 178 ms
43,784 KB |
testcase_04 | AC | 178 ms
43,960 KB |
testcase_05 | AC | 190 ms
44,108 KB |
testcase_06 | AC | 195 ms
43,844 KB |
testcase_07 | AC | 198 ms
43,804 KB |
testcase_08 | AC | 195 ms
43,712 KB |
testcase_09 | AC | 197 ms
43,824 KB |
testcase_10 | AC | 201 ms
44,484 KB |
testcase_11 | AC | 198 ms
43,632 KB |
testcase_12 | AC | 209 ms
44,116 KB |
testcase_13 | AC | 195 ms
43,668 KB |
testcase_14 | AC | 178 ms
44,108 KB |
testcase_15 | AC | 3,612 ms
109,992 KB |
testcase_16 | AC | 4,206 ms
127,688 KB |
testcase_17 | AC | 3,718 ms
103,256 KB |
testcase_18 | AC | 4,257 ms
125,272 KB |
testcase_19 | AC | 4,275 ms
131,068 KB |
testcase_20 | AC | 4,048 ms
124,764 KB |
testcase_21 | AC | 4,274 ms
133,860 KB |
testcase_22 | AC | 4,118 ms
126,468 KB |
testcase_23 | AC | 3,734 ms
107,992 KB |
testcase_24 | AC | 4,328 ms
132,732 KB |
testcase_25 | AC | 4,635 ms
142,536 KB |
testcase_26 | AC | 4,637 ms
142,192 KB |
testcase_27 | AC | 4,003 ms
126,028 KB |
testcase_28 | AC | 3,140 ms
88,276 KB |
testcase_29 | AC | 3,160 ms
87,256 KB |
testcase_30 | AC | 2,611 ms
90,140 KB |
testcase_31 | AC | 2,460 ms
81,456 KB |
testcase_32 | AC | 2,416 ms
83,300 KB |
testcase_33 | AC | 2,463 ms
83,592 KB |
testcase_34 | AC | 2,793 ms
95,868 KB |
testcase_35 | AC | 3,737 ms
151,056 KB |
testcase_36 | AC | 2,440 ms
90,960 KB |
testcase_37 | AC | 3,137 ms
132,492 KB |
testcase_38 | AC | 3,064 ms
126,852 KB |
testcase_39 | AC | 2,795 ms
116,304 KB |
testcase_40 | AC | 2,801 ms
114,784 KB |
testcase_41 | AC | 144 ms
41,576 KB |
testcase_42 | AC | 151 ms
41,704 KB |
testcase_43 | AC | 150 ms
41,804 KB |
ソースコード
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); PriorityQueue<Path> queue = new PriorityQueue<>(); queue.add(new Path((sc.nextInt() - 1) * w + sc.nextInt() - 1, 1, 0)); int[] field = new int[h * w]; ArrayList<TreeMap<Integer, Integer>> costs = new ArrayList<>(); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { field[i * w + j] = sc.nextInt(); costs.add(new TreeMap<>()); } } while (queue.size() > 0) { Path p = queue.poll(); if (costs.get(p.idx).size() > 0 && costs.get(p.idx).lastEntry().getValue() <= p.value) { continue; } costs.get(p.idx).put(p.count, p.value); if (p.idx % w > 0) { queue.add(new Path(p.idx - 1, p.count + 1, p.value + field[p.idx])); } if (p.idx % w < w - 1) { queue.add(new Path(p.idx + 1, p.count + 1, p.value + field[p.idx])); } if (p.idx / w > 0) { queue.add(new Path(p.idx - w, p.count + 1, p.value + field[p.idx])); } if (p.idx / w < h - 1) { queue.add(new Path(p.idx + w, p.count + 1, p.value + field[p.idx])); } } StringBuilder sb = new StringBuilder(); int q = sc.nextInt(); for (int i = 0; i < q; i++) { int idx = (sc.nextInt() - 1) * w + sc.nextInt() - 1; long k = sc.nextInt(); k *= k; long ans = Long.MAX_VALUE; for (Map.Entry<Integer, Integer> entry : costs.get(idx).entrySet()) { int key = entry.getKey(); int value = entry.getValue(); ans = Math.min(ans, k * key + value + field[idx]); } sb.append(ans).append("\n"); } System.out.print(sb); } static class Path implements Comparable<Path> { int idx; int count; int value; public Path(int idx, int count, int value) { this.idx = idx; this.count = count; this.value = value; } public int compareTo(Path another) { if (count == another.count) { return value - another.value; } else { return count - another.count; } } } }