結果

問題 No.1 道のショートカット
ユーザー ym678ym678
提出日時 2016-07-23 19:15:52
言語 Java21
(openjdk 21)
結果
MLE  
実行時間 -
コード長 2,334 bytes
コンパイル時間 2,426 ms
コンパイル使用メモリ 79,812 KB
実行使用メモリ 743,172 KB
最終ジャッジ日時 2024-07-08 04:29:43
合計ジャッジ時間 11,106 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 136 ms
41,200 KB
testcase_01 AC 140 ms
41,276 KB
testcase_02 AC 135 ms
41,188 KB
testcase_03 AC 142 ms
41,260 KB
testcase_04 AC 123 ms
40,408 KB
testcase_05 AC 139 ms
41,632 KB
testcase_06 AC 144 ms
41,436 KB
testcase_07 AC 149 ms
41,620 KB
testcase_08 AC 249 ms
47,192 KB
testcase_09 AC 223 ms
44,680 KB
testcase_10 AC 260 ms
47,744 KB
testcase_11 MLE -
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