結果

問題 No.1 道のショートカット
ユーザー ayemosayemos
提出日時 2015-05-15 11:18:16
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 4,038 bytes
コンパイル時間 2,728 ms
コンパイル使用メモリ 80,796 KB
実行使用メモリ 154,432 KB
最終ジャッジ日時 2024-07-08 04:00:10
合計ジャッジ時間 9,168 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
36,944 KB
testcase_01 AC 54 ms
36,968 KB
testcase_02 AC 55 ms
37,064 KB
testcase_03 AC 56 ms
37,016 KB
testcase_04 WA -
testcase_05 AC 55 ms
37,116 KB
testcase_06 AC 55 ms
37,064 KB
testcase_07 AC 56 ms
36,860 KB
testcase_08 AC 99 ms
39,088 KB
testcase_09 AC 80 ms
38,340 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 54 ms
37,180 KB
testcase_16 WA -
testcase_17 AC 56 ms
36,972 KB
testcase_18 AC 58 ms
37,112 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 59 ms
36,808 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 95 ms
38,716 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 57 ms
37,172 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 74 ms
37,328 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 58 ms
36,500 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 AC 56 ms
36,672 KB
testcase_43 AC 57 ms
36,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final String LINE_SPR = System.getProperty("line.separator");
    final int BIG_MOD = 1000000007;

    class Proc {
        int index;
        int money;
        int time;

        public Proc(int index, int money, int time) {
            this.index = index;
            this.money = money;
            this.time  = time;
        }

        public int hashCode() {
            return index + money * 31 + time * 31 * 31;
        }

        public boolean equals(Object obj) {
            if(obj instanceof Proc) {
                Proc proc = (Proc)obj;
                return index == proc.index && money == proc.money && time == time;
            } else {
                return false;
            }
        }

        public String toString() {
            return "PROC(" + index + ":" + money + ":" + time + ")";
        }
    }

    void run() throws Exception {
        String line;
        int n = ni();
        int c = ni();
        int v = ni();
        int[][] graph = new int[n][n];
        int[][] costs = new int[n][n];
        String[] sstr = ns().split(" ");
        String[] tstr = ns().split(" ");
        String[] ystr = ns().split(" ");
        String[] mstr = ns().split(" ");

        for(int i = 0; i < v; i++)  {
            int s, t, y, m;
            s = Integer.parseInt(sstr[i]);
            t = Integer.parseInt(tstr[i]);
            y = Integer.parseInt(ystr[i]);
            m = Integer.parseInt(mstr[i]);
            graph[s-1][t-1] = m;
            costs[s-1][t-1] = y;
        }


        Proc init = new Proc(1, c, 0);
        Deque<Proc> queue = new ArrayDeque<Proc>();
        int res = Integer.MAX_VALUE;
        queue.offer(init);
        while(!queue.isEmpty()) {
            Proc proc = queue.poll();
            if(proc.index == n) {
                res = Math.min(res, proc.time);
                continue;
            }

            for(int t = 0; t < n; t++) {
                int s = proc.index - 1;
                if(graph[s][t] > 0 &&
                        costs[s][t] <= proc.money) {
                    // affordable
                    queue.offer(new Proc(t + 1, proc.money - costs[s][t],
                                proc.time + graph[s][t]));
                }
            }
        }

        System.out.println(res == Integer.MAX_VALUE ? -1 : res);
    }


    /*
     * Templates
     */
    void dumpObjArr(Object[] arr, int n) {
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i]);
            if(i < n - 1)
                System.out.print(" ");
        }
        System.out.println("");
    }

    void dumpObjArr2(Object[][] arr, int m, int n) {
        for(int j = 0; j < m; j++) 
            dumpObjArr(arr[j], n);
    }

    int ni() throws Exception {
        return Integer.parseInt(br.readLine().trim());
    }

    long nl() throws Exception {
        return Long.parseLong(br.readLine().trim());
    }

    String ns() throws Exception {
        return br.readLine();
    }

    boolean isPrime(int n) {
        for(int i=2;i<n;i++) {
            if(n%i==0)
                return false;
        }
        return true;
    }

    int getPrime(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        int count = 1;

        int x = 1;
        while(primes.size() < n) {
            x+=2;
            int m = (int)Math.sqrt(x);
            for(int p : primes) {
                if(p > m) {
                    primes.add(x);
                    break;
                }

                if(x % p == 0) 
                    break;
            }
        }

        return primes.get(primes.size() - 1);
    }

    void gcjPrint(String str, int t) {
        System.out.println("Case #" + t + ": " + str);
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
}
0