結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-07-29 22:55:55 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 172 ms / 5,000 ms |
コード長 | 1,855 bytes |
コンパイル時間 | 2,656 ms |
コンパイル使用メモリ | 77,608 KB |
実行使用メモリ | 40,696 KB |
最終ジャッジ日時 | 2024-07-20 16:16:36 |
合計ジャッジ時間 | 7,280 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int C = Integer.parseInt(br.readLine()); int V = Integer.parseInt(br.readLine()); int[] S = convert(br.readLine().split(" "));//from int[] T = convert(br.readLine().split(" "));//to int[] Y = convert(br.readLine().split(" "));//費用 int[] M = convert(br.readLine().split(" "));//時間 int[][] min = new int[N + 1][C + 1]; for (int i = 2; i <= N; i++) { Arrays.fill(min[i], Integer.MAX_VALUE); } for (int i = 1; i <= N; i++) { for (int j = 0; j < V; j++) { int tmpS = S[j]; int tmpT = T[j]; int tmpY = Y[j]; int tmpM = M[j]; for (int k = 0; k + tmpY <= C; k++) { if (min[tmpS][k] != Integer.MAX_VALUE && min[tmpS][k] + tmpM < min[tmpT][k + tmpY]) { min[tmpT][k + tmpY] = min[tmpS][k] + tmpM; } } } } int minTime = Integer.MAX_VALUE; for (int i = 0; i <= C; i++) { if (min[N][i] < minTime) { minTime = min[N][i]; } } if (minTime == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(minTime); } } private static int[] convert(String[] source) { int[] dest = new int[source.length]; for (int i = 0; i < source.length; i++) { dest[i] = Integer.parseInt(source[i]); } return dest; } }