結果

問題 No.496 ワープクリスタル (給料日前編)
コンテスト
ユーザー zimpha
提出日時 2017-03-25 17:48:08
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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