結果
問題 | No.867 避難経路 |
ユーザー |
![]() |
提出日時 | 2021-03-04 20:17:07 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 3,571 ms / 6,000 ms |
コード長 | 2,573 bytes |
コンパイル時間 | 2,747 ms |
コンパイル使用メモリ | 80,368 KB |
実行使用メモリ | 150,160 KB |
最終ジャッジ日時 | 2024-10-05 08:27:34 |
合計ジャッジ時間 | 86,155 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
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;}}}}