結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2020-05-11 19:28:29 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 248 ms / 5,000 ms |
コード長 | 1,926 bytes |
コンパイル時間 | 3,742 ms |
コンパイル使用メモリ | 79,364 KB |
実行使用メモリ | 46,116 KB |
最終ジャッジ日時 | 2024-07-20 16:47:53 |
合計ジャッジ時間 | 11,768 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int c = sc.nextInt(); int size = sc.nextInt(); int[] starts = new int[size]; int[] ends = new int[size]; int[] costs = new int[size]; int[] times = new int[size]; for (int i = 0; i < size; i++) { starts[i] = sc.nextInt() - 1; } for (int i = 0; i < size; i++) { ends[i] = sc.nextInt() - 1; } for (int i = 0; i < size; i++) { costs[i] = sc.nextInt(); } for (int i = 0; i < size; i++) { times[i] = sc.nextInt(); } ArrayList<ArrayList<Path>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < size; i++) { graph.get(starts[i]).add(new Path(ends[i], costs[i], times[i])); } PriorityQueue<Path> queue = new PriorityQueue<>(); queue.add(new Path(0, c, 0)); int[] values = new int[n]; Arrays.fill(values, Integer.MAX_VALUE); while (queue.size() > 0) { Path p = queue.poll(); if (values[p.idx] <= p.time) { continue; } values[p.idx] = p.time; for (Path x : graph.get(p.idx)) { if (x.cost > p.cost) { continue; } queue.add(new Path(x.idx, p.cost - x.cost, p.time + x.time)); } } if (values[n - 1] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(values[n - 1]); } } static class Path implements Comparable<Path> { int idx; int cost; int time; public Path(int idx, int cost, int time) { this.idx = idx; this.cost = cost; this.time = time; } public int compareTo(Path another) { if (cost == another.cost) { return time - another.time; } else { return another.cost - cost; } } } }