結果

問題 No.1 道のショートカット
ユーザー ym678ym678
提出日時 2016-07-23 18:45:10
言語 Java21
(openjdk 21)
結果
MLE  
実行時間 -
コード長 2,307 bytes
コンパイル時間 2,912 ms
コンパイル使用メモリ 80,348 KB
実行使用メモリ 751,392 KB
最終ジャッジ日時 2024-07-08 04:29:14
合計ジャッジ時間 11,019 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
54,088 KB
testcase_01 AC 132 ms
54,104 KB
testcase_02 AC 130 ms
53,836 KB
testcase_03 AC 138 ms
54,120 KB
testcase_04 AC 129 ms
53,876 KB
testcase_05 AC 117 ms
52,800 KB
testcase_06 AC 137 ms
54,228 KB
testcase_07 AC 142 ms
53,992 KB
testcase_08 MLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
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 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)
    	ArrayList<tpl> copy = new ArrayList<>(triple);   	
    	List.add(copy);
    	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++){
    		            triple.add(new tpl(from[j], cost[j] + sub.get(t).get_cost(),
    		            		       time[j] + sub.get(t).get_time()));   		    	    
    		    	}
    		    }
    		}
    		ArrayList<tpl> copy_2 = new ArrayList<>(triple);
    		List.add(copy_2);
    		triple.clear();
    	}
    	//最短経路を取り出す
    	triple = List.get(town-1);
    	if(triple.isEmpty()){
    		System.out.println(-1);
    	}else{
    	    int c;
    	    ArrayList<Integer> sort = new ArrayList();
    	    for(int i=0; i<triple.size(); i++){
    		    if(triple.get(i).get_cost() <= money){
    			    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