結果

問題 No.1 道のショートカット
コンテスト
ユーザー Amanita2016
提出日時 2017-09-16 16:37:40
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,877 bytes
コンパイル時間 3,042 ms
コンパイル使用メモリ 77,444 KB
実行使用メモリ 55,356 KB
最終ジャッジ日時 2024-07-08 04:57:29
合計ジャッジ時間 7,908 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 WA * 32 RE * 5
権限があれば一括ダウンロードができます

ソースコード

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