結果
| 問題 | No.614 壊れたキャンパス |
| ユーザー |
 Grenache
|
| 提出日時 | 2018-01-07 11:52:10 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,979 ms / 2,000 ms |
| コード長 | 6,175 bytes |
| コンパイル時間 | 3,971 ms |
| コンパイル使用メモリ | 82,212 KB |
| 実行使用メモリ | 140,752 KB |
| 最終ジャッジ日時 | 2024-12-23 09:56:24 |
| 合計ジャッジ時間 | 18,862 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
import java.io.*;import java.util.*;import java.util.Map.*;public class Main_yukicoder614 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();int m = sc.nextInt();@SuppressWarnings("unused")int k = sc.nextInt();int s = sc.nextInt();int t = sc.nextInt();int[] a = new int[m];int[] b = new int[m];int[] c = new int[m];List<List<Integer>> edges = new ArrayList<>(n - 1);for (int i = 0; i < n - 1; i++) {edges.add(new ArrayList<>());}for (int i = 0; i < m; i++) {a[i] = sc.nextInt() - 1;b[i] = sc.nextInt();c[i] = sc.nextInt();edges.get(a[i]).add(i);}final long INF = Long.MAX_VALUE / 4;Map<Integer, Long> pre = new TreeMap<>();pre.put(s, 0L);for (int i = 0; i < n - 1; i++) {Map<Integer, Long> tm = new TreeMap<>();tm.putAll(pre);for (int e : edges.get(i)) {if (!tm.containsKey(b[e])) {tm.put(b[e], INF);}}List<Integer> list = new ArrayList<>(tm.keySet());Collections.sort(list);// /*for (int j = 1, size = list.size(); j < size; j++) {int p = list.get(j - 1);int e = list.get(j);tm.put(e, Math.min(tm.get(p) + e - p, tm.get(e)));}for (int j = list.size() - 2; j >= 0; j--) {int ne = list.get(j + 1);int e = list.get(j);tm.put(e, Math.min(tm.get(ne) + ne - e, tm.get(e)));}// *//*for (int j = 0, size = list.size(); j < size; j++) {int e = list.get(j);for (int j2 = 0; j2 < size; j2++) {int e2 = list.get(j2);if (j != j2) {tm.put(e, Math.min(tm.get(e2) + Math.abs(e2 - e), tm.get(e)));}}}// */pre.clear();for (int e : edges.get(i)) {if (pre.containsKey(c[e])) {pre.put(c[e], Math.min(tm.get(b[e]), pre.get(c[e])));} else {pre.put(c[e], tm.get(b[e]));}}// *//*tm = new TreeMap<>();for (int e : edges.get(i)) {long min = INF;for (Entry<Integer, Long> e2 : pre.entrySet()) {min = Math.min(min, Math.abs(e2.getKey() - b[e]) + e2.getValue());}if (tm.containsKey(c[e])) {tm.put(c[e], Math.min(min, tm.get(c[e])));} else {tm.put(c[e], min);}}pre = tm;// */}long ans = INF;for (Entry<Integer, Long> e : pre.entrySet()) {ans = Math.min(ans, Math.abs(e.getKey() - t) + e.getValue());}if (ans == INF) {pr.println(-1);} else {pr.println(ans);}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}