結果

問題 No.496 ワープクリスタル (給料日前編)
ユーザー zimphazimpha
提出日時 2017-03-25 17:48:08
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 5,195 bytes
コンパイル時間 2,455 ms
コンパイル使用メモリ 84,124 KB
実行使用メモリ 47,012 KB
最終ジャッジ日時 2024-07-06 06:05:03
合計ジャッジ時間 5,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
37,520 KB
testcase_01 AC 47 ms
37,124 KB
testcase_02 AC 46 ms
37,208 KB
testcase_03 AC 45 ms
37,284 KB
testcase_04 WA -
testcase_05 AC 47 ms
37,012 KB
testcase_06 AC 76 ms
40,284 KB
testcase_07 AC 48 ms
37,520 KB
testcase_08 AC 171 ms
44,288 KB
testcase_09 AC 431 ms
47,012 KB
testcase_10 WA -
testcase_11 AC 48 ms
37,412 KB
testcase_12 WA -
testcase_13 AC 87 ms
40,048 KB
testcase_14 AC 127 ms
42,720 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 139 ms
45,812 KB
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Chiaki.Hoshinomori
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task496 solver = new Task496();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task496 {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int q = in.nextInt();
            int f = in.nextInt();
            int[][] dis = new int[n * 2 + 1][];
            boolean[][] vis = new boolean[n * 2 + 1][];
            for (int i = 0; i <= n * 2; ++i) {
                dis[i] = new int[m * 2 + 1];
                vis[i] = new boolean[m * 2 + 1];
                Arrays.fill(dis[i], (n + m) * f);
            }
            int[] sx = new int[q];
            int[] sy = new int[q];
            int[] sc = new int[q];
            for (int i = 0; i < q; i++) {
                sx[i] = in.nextInt();
                sy[i] = in.nextInt();
                sc[i] = in.nextInt();
            }
            Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
            queue.add(new Pair<>(0, 0));
            dis[0][0] = 0;
            vis[0][0] = true;
            int[] dx = new int[]{1, -1, 0, 0};
            int[] dy = new int[]{0, 0, 1, -1};
            while (!queue.isEmpty()) {
                Pair<Integer, Integer> a = queue.poll();
                vis[a.first][a.second] = false;
                for (int i = 0; i < q; ++i) {
                    int x = a.first + sx[i];
                    int y = a.second + sy[i];
                    if (x <= n * 2 && y <= m * 2 && dis[x][y] > dis[a.first][a.second] + sc[i]) {
                        dis[x][y] = dis[a.first][a.second] + sc[i];
                        if (!vis[x][y]) {
                            vis[x][y] = true;
                            queue.add(new Pair<>(x, y));
                        }
                    }
                }
                for (int i = 0; i < 4; ++i) {
                    int x = a.first + dx[i];
                    int y = a.second + dy[i];
                    if (x <= n * 2 && y <= m * 2 && x >= 0 && y >= 0 && dis[x][y] > dis[a.first][a.second] + f) {
                        dis[x][y] = dis[a.first][a.second] + f;
                        if (!vis[x][y]) {
                            vis[x][y] = true;
                            queue.add(new Pair<>(x, y));
                        }
                    }
                }
            }
            out.println(dis[n][m]);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class Pair<A, B> {
        public A first;
        public B second;

        public Pair(A first, B second) {
            super();
            this.first = first;
            this.second = second;
        }

        public int hashCode() {
            int hashFirst = first != null ? first.hashCode() : 0;
            int hashSecond = second != null ? second.hashCode() : 0;

            return (hashFirst + hashSecond) * hashSecond + hashFirst;
        }

        public boolean equals(Object other) {
            if (other instanceof Pair) {
                Pair otherPair = (Pair) other;
                return
                        ((this.first == otherPair.first ||
                                (this.first != null && otherPair.first != null &&
                                        this.first.equals(otherPair.first))) &&
                                (this.second == otherPair.second ||
                                        (this.second != null && otherPair.second != null &&
                                                this.second.equals(otherPair.second))));
            }

            return false;
        }

        public String toString() {
            return "(" + first + ", " + second + ")";
        }

    }
}
0