結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2014-11-12 23:06:48 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 248 ms / 5,000 ms |
コード長 | 1,717 bytes |
コンパイル時間 | 4,153 ms |
コンパイル使用メモリ | 78,428 KB |
実行使用メモリ | 46,252 KB |
最終ジャッジ日時 | 2024-07-20 16:07:10 |
合計ジャッジ時間 | 12,966 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class ShortCut { public static void main(String[] args) { ShortCut p = new ShortCut(); } public ShortCut() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c = sc.nextInt(); int v = sc.nextInt(); Edge[] e = new Edge[v]; for(int i=0;i<e.length;i++) e[i] = new Edge(); for(int i=0;i<e.length;i++) e[i].s = sc.nextInt(); for(int i=0;i<e.length;i++) e[i].t = sc.nextInt(); for(int i=0;i<e.length;i++) e[i].y = sc.nextInt(); for(int i=0;i<e.length;i++) e[i].m = sc.nextInt(); solve(n, c, v, e); } private final int INF = 1000000; private void solve(int n, int c, int v, Edge[] edge) { Arrays.sort(edge); // dp[i,j] : 1からiへコストjで行く時の最小時間 int[][] dp = new int[50+1][300+1]; for(int i=2;i<dp.length;i++) Arrays.fill(dp[i], INF); for(int i=0;i<edge.length;i++){ Edge e = edge[i]; for(int j=1;j<dp[e.t].length;j++){ if(j-e.y >= 0) dp[e.t][j] = Math.min(dp[e.t][j], Math.min(dp[e.s][j-e.y] + e.m, dp[e.t][j-1])); } } int res = INF; for(int i=1;i<=c;i++){ res = Math.min(res, dp[n][i]); } if(res >= INF) System.out.println(-1); else System.out.println(res); } private class Edge implements Comparable<Edge>{ int s; int t; int y; int m; public Edge(int s, int t, int y, int m) { this.s = s; this.t = t; this.y = y; this.m = m; } public Edge() { } @Override public int compareTo(Edge o) { if(this.s != o.s) return this.s - o.s; else return this.t - o.t; } } }