結果

問題 No.1 道のショートカット
ユーザー ym678
提出日時 2016-07-23 19:15:52
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 MLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

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