結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 2021-07-21 11:46:41 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,288 bytes |
コンパイル時間 | 5,001 ms |
コンパイル使用メモリ | 80,992 KB |
実行使用メモリ | 236,500 KB |
最終ジャッジ日時 | 2024-07-17 13:54:32 |
合計ジャッジ時間 | 13,344 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 TLE * 8 |
ソースコード
import java.io.*;import java.util.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();int s = sc.nextInt();int t = sc.nextInt();ArrayList<TreeSet<Integer>> floors = new ArrayList<>();ArrayList<HashMap<Integer, Long>> dp = new ArrayList<>();ArrayList<HashMap<Integer, ArrayList<Integer>>> graph = new ArrayList<>();for (int i = 0; i < n; i++) {floors.add(new TreeSet<>());dp.add(new HashMap<>());graph.add(new HashMap<>());}floors.get(0).add(s);floors.get(n - 1).add(t);for (int i = 0; i < m; i++) {int a = sc.nextInt() - 1;int b = sc.nextInt();int c = sc.nextInt();floors.get(a).add(b);floors.get(a + 1).add(c);if (!graph.get(a).containsKey(b)) {graph.get(a).put(b, new ArrayList<>());}graph.get(a).get(b).add(c);}PriorityQueue<Path> queue = new PriorityQueue<>();queue.add(new Path(0, s, 0));while (queue.size() > 0) {Path p = queue.poll();if (dp.get(p.idx).containsKey(p.floor)) {continue;}dp.get(p.idx).put(p.floor, p.value);if (floors.get(p.idx).first() != p.floor) {int next = floors.get(p.idx).lower(p.floor);queue.add(new Path(p.idx, next, p.value + p.floor - next));}if (floors.get(p.idx).last() != p.floor) {int next = floors.get(p.idx).higher(p.floor);queue.add(new Path(p.idx, next, p.value + next - p.floor));}if (graph.get(p.idx).containsKey(p.floor)) {for (int x : graph.get(p.idx).get(p.floor)) {queue.add(new Path(p.idx + 1, x, p.value));}}}System.out.println(dp.get(n - 1).getOrDefault(t, -1L));}static class Path implements Comparable<Path> {int idx;int floor;long value;public Path(int idx, int floor, long value) {this.idx = idx;this.floor = floor;this.value = value;}public int compareTo(Path another) {if (value == another.value) {return 0;} else if (value < another.value) {return -1;} else {return 1;}}}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public String next() throws Exception {if (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}