結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-11-08 11:50:48 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,869 bytes |
コンパイル時間 | 2,418 ms |
コンパイル使用メモリ | 79,648 KB |
実行使用メモリ | 52,180 KB |
最終ジャッジ日時 | 2024-07-08 03:35:18 |
合計ジャッジ時間 | 10,975 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 TLE * 1 -- * 32 |
ソースコード
import java.util.*; class miti{ int now; int to; int cost; int time; miti(int now,int to,int cost,int time){ this.now = now; this.to = to; this.cost=cost; this.time = time; } } class mitiComparator implements Comparator<miti>{ @Override public int compare(miti o1, miti o2) { if(o1.now>o2.now){ return 1; }else if(o1.now==o2.now){ return 0; }else{ return -1; } } } public class Main { static int ans=Integer.MAX_VALUE; static void dfs(int now,int nowcost,int nowtime,int goal,ArrayList<miti>[] mitilist,int limcost){ if(now==goal){ ans=Math.min(nowtime,ans); } if(mitilist[now]==null) return; for(int i=0;i<mitilist[now].size();i++){ if(nowcost+mitilist[now].get(i).cost>limcost){ continue; } dfs(+mitilist[now].get(i).to,nowcost+mitilist[now].get(i).cost,nowtime+mitilist[now].get(i).time,goal,mitilist,limcost); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N=sc.nextInt(); int C =sc.nextInt(); int V=sc.nextInt(); int[] S = new int[V]; int[] T = new int[V]; int[] Y = new int[V]; int[] M=new int[V]; for(int i=0;i<V;i++){ S[i]=sc.nextInt(); } for(int i=0;i<V;i++){ T[i]=sc.nextInt(); } for(int i=0;i<V;i++){ Y[i]=sc.nextInt(); } for(int i=0;i<V;i++){ M[i]=sc.nextInt(); } miti[] miti1=new miti[V]; for(int i=0;i<V;i++){ miti1[i]=new miti(S[i],T[i],Y[i],M[i]); } Arrays.sort(miti1,new mitiComparator()); ArrayList<miti>[] mitilist = new ArrayList[V+1]; for(miti a:miti1){ if(mitilist[a.now]==null){ mitilist[a.now]=new ArrayList<miti>(); } mitilist[a.now].add(a); } dfs(1,0,0,N,mitilist,C); if(ans==Integer.MAX_VALUE){ System.out.println(-1); }else{ System.out.println(ans); } } }