結果

問題 No.1 道のショートカット
ユーザー Amanita2016Amanita2016
提出日時 2017-09-16 16:37:40
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 1,877 bytes
コンパイル時間 3,423 ms
コンパイル使用メモリ 73,944 KB
実行使用メモリ 55,416 KB
最終ジャッジ日時 2023-09-22 13:14:22
合計ジャッジ時間 8,097 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
49,112 KB
testcase_01 AC 43 ms
49,280 KB
testcase_02 AC 42 ms
49,340 KB
testcase_03 AC 42 ms
49,140 KB
testcase_04 AC 42 ms
49,448 KB
testcase_05 AC 42 ms
49,304 KB
testcase_06 AC 43 ms
49,144 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 RE -
testcase_16 WA -
testcase_17 RE -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 RE -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 RE -
testcase_43 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Shortcut {

	private static BufferedReader br;

	public static void main(String[] args) throws IOException{
		br = new BufferedReader(new InputStreamReader(System.in));
		int town = Integer.parseInt(br.readLine());
		int money = Integer.parseInt(br.readLine());
		int road = Integer.parseInt(br.readLine());
		road++;
		int[] s = new int[road];
		int[] t = new int[road];
		int[] y = new int[road];
		int[] m = new int[road];
		arrayInit(s);
		arrayInit(t);
		arrayInit(y);
		arrayInit(m);
		//Library.disp(Library.cast(m));
		int dp[][] = new int[3][road]; // cost time
		while(true){
			for(int i = 1 ; i < road; i++){
				dp[0][i] = 0;
				dp[1][i] = 0;
				dp[2][i] = -1;
			}
			for(int i = 1 ; i < road ; i++){
				int from = s[i];
				if(from == -1){
					continue;
				}
				int to = t[i];
				int fCost = dp[0][from];
				int fTime = dp[1][from];
				int tTime = dp[1][to];
				int totalCost = y[i] + fCost;
				int totalTime = m[i] + fTime;
				if((tTime == 0 || totalTime < tTime) && totalCost <= money ){
					dp[0][to] = totalCost;
					dp[1][to] = totalTime;
					dp[2][to] = i;
				}

			}
			int time = dp[1][road-1];
			if(time == 0){
				int max = -1;
				for(int i = 1 ; i < road ; i++){
					int from = dp[2][i];
					if(max < from){
						max = from;
					}
				}
				if(max == -1){
					break;
				}
				s[max] = -1;
				continue;
			}
			break;
		}
		int time = dp[1][road-1];
		int disp = time == 0 ? -1 : time;
		System.out.println(disp);
	}

	private static void arrayInit(int[] array) throws IOException{
		String[] spl = br.readLine().split(" ");
		for(int i = 1 ; i < array.length ; i++){
			array[i] = Integer.parseInt(spl[i-1]);
		}
	}

}
0