結果

問題 No.1 道のショートカット
ユーザー ym678ym678
提出日時 2016-07-23 19:15:52
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,334 bytes
コンパイル時間 3,985 ms
コンパイル使用メモリ 76,024 KB
実行使用メモリ 60,744 KB
最終ジャッジ日時 2023-09-22 12:46:13
合計ジャッジ時間 12,060 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
56,084 KB
testcase_01 AC 127 ms
56,092 KB
testcase_02 AC 127 ms
55,992 KB
testcase_03 AC 132 ms
55,668 KB
testcase_04 AC 126 ms
55,872 KB
testcase_05 AC 128 ms
55,880 KB
testcase_06 AC 132 ms
55,504 KB
testcase_07 AC 139 ms
55,852 KB
testcase_08 AC 235 ms
60,508 KB
testcase_09 AC 205 ms
59,040 KB
testcase_10 AC 239 ms
60,744 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main{	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in); 
    	ArrayList<ArrayList<tpl>> List = new ArrayList<>();
    	ArrayList<tpl> triple = new ArrayList<>();
    	int MAX = Integer.MAX_VALUE / 4;
    	int town = sc.nextInt();
    	int money = sc.nextInt();
    	int ru = sc.nextInt();
    	
    	int[] from = new int[ru];
    	int[] to = new int[ru];
    	int[] cost = new int[ru];
    	int[] time = new int[ru];
    	
    	for(int i=0; i<ru ;i++){//入力
    		from[i] = sc.nextInt();
    	}
    	for(int i=0; i<ru ;i++){//入力
    		to[i] = sc.nextInt();
    	}
    	for(int i=0; i<ru ;i++){//入力
    		cost[i] = sc.nextInt();
    	}
    	for(int i=0; i<ru ;i++){//入力
    		time[i] = sc.nextInt();
    	}
    	
    	triple.add(new tpl(0,0,0));//初期位置 (from = 0)  	
    	List.add(new ArrayList<>(triple));
    	triple.clear();
    	
    	for(int i=2; i<=town ;i++){//二番目の町から
    		for(int j=0; j<ru ;j++){
    		    if(to[j] == i){
                    ArrayList<tpl> sub = new ArrayList<>(List.get(from[j]-1));
    		    	for(int t=0; t<sub.size(); t++){
    		    		if(cost[j] + sub.get(t).get_cost() <= money &&
    		    		   time[j] + sub.get(t).get_time() <= MAX){
    		                triple.add(new tpl(from[j], cost[j] + sub.get(t).get_cost(),
    		            		           time[j] + sub.get(t).get_time()));  
    		    		}
    		    	}
    		    }
    		}
    		List.add(new ArrayList<>(triple));
    		triple.clear();
    	}
    	//最短経路を取り出す
    	triple = List.get(town-1);
    	if(triple.isEmpty()){
    		System.out.println(-1);
    	}else{
    	    ArrayList<Integer> sort = new ArrayList<>();
    	    for(int i=0; i<triple.size(); i++){
    	        sort.add(triple.get(i).get_time());
    		}
    	    if(sort.isEmpty()){
    	    	System.out.println(-1);
    	    }else{
    	        Collections.sort(sort);
    	        System.out.println(sort.get(0));
    	    }
    	}
    }
    
    public static class tpl{
    	int town_from;
    	int cost;
    	int time;
    	tpl(int from, int cost, int time){
    		this.town_from = from;
    		this.cost = cost;
    		this.time = time;
    	}
    	int get_cost(){
    		return cost;
    	}
    	int get_time(){
    		return time;
    	}
    }
}
0