結果

問題 No.1 道のショートカット
ユーザー CrazyBBB
提出日時 2016-03-05 18:15:11
言語 Java
(openjdk 23)
結果
AC  
実行時間 338 ms / 5,000 ms
コード長 1,165 bytes
コンパイル時間 2,158 ms
コンパイル使用メモリ 77,176 KB
実行使用メモリ 47,268 KB
最終ジャッジ日時 2024-07-20 16:22:09
合計ジャッジ時間 12,765 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class Main {

	static int[] S;
	static int[] T;
	static int[] Y;
	static int[] M;
	static int[][] dp;
	static final int INF = Integer.MAX_VALUE/2;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int C = sc.nextInt();
		int V = sc.nextInt();
		dp = new int[N][C+1];
		S = new int[V];
		for (int i=0; i<V; i++) {
			S[i] = sc.nextInt()-1;
		}
		T = new int[V];
		for (int i=0; i<V; i++) {
			T[i] = sc.nextInt()-1;
		}
		Y = new int[V];
		for (int i=0; i<V; i++) {
			Y[i] = sc.nextInt();
		}
		M = new int[V];
		for (int i=0; i<V; i++) {
			M[i] = sc.nextInt();
		}

		for (int i=0; i<N; i++) {
			for (int j=0; j<=C; j++) {
				dp[i][j] = INF;
			}
		}
		for (int i=0; i<=C; i++) {
			dp[0][i] = 0;
		}

		for (int i=0; i<N; i++) {
			for (int j=0; j<=C; j++) {
				for (int k=0; k<V; k++) {
					if (S[k] == i) {
						if (j+Y[k]<=C) {
							dp[T[k]][j+Y[k]] = Math.min(dp[T[k]][j+Y[k]], dp[i][j]+M[k]);
						}
					}
				}
			}
		}

		int ans = dp[N-1][C];
		if (ans == INF) {
			System.out.println(-1);
		} else {
			System.out.println(ans);
		}

		sc.close();
	}
}
0