結果
| 問題 | No.1868 Teleporting Cyanmond |
| ユーザー |
 shojin_pro
|
| 提出日時 | 2022-03-11 21:23:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 306 ms / 2,000 ms |
| コード長 | 10,233 bytes |
| コンパイル時間 | 3,625 ms |
| コンパイル使用メモリ | 94,864 KB |
| 実行使用メモリ | 61,712 KB |
| 最終ジャッジ日時 | 2024-09-16 01:20:22 |
| 合計ジャッジ時間 | 9,699 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
import java.util.*;import java.io.*;public class Main {static ContestScanner sc = new ContestScanner(System.in);static PrintWriter pw = new PrintWriter(System.out);static StringBuilder sb = new StringBuilder();static long mod = (long) 1e9 + 7;public static void main(String[] args) throws Exception {solve();pw.flush();}public static void solve() {int N = sc.nextInt();Dijkstra dijk = new Dijkstra(N);for(int i = 0; i < N-1; i++){dijk.addEdge(i,sc.nextInt()-1,1);if(i != 0){dijk.addEdge(i,i-1,0);}}dijk.addEdge(N-1,N-2,0);pw.println(dijk.dijkstra(0,N)[N-1]);}static class GeekInteger {public static void save_sort(int[] array) {shuffle(array);Arrays.sort(array);}public static int[] shuffle(int[] array) {int n = array.length;Random random = new Random();for (int i = 0, j; i < n; i++) {j = i + random.nextInt(n - i);int randomElement = array[j];array[j] = array[i];array[i] = randomElement;}return array;}public static void save_sort(long[] array) {shuffle(array);Arrays.sort(array);}public static long[] shuffle(long[] array) {int n = array.length;Random random = new Random();for (int i = 0, j; i < n; i++) {j = i + random.nextInt(n - i);long randomElement = array[j];array[j] = array[i];array[i] = randomElement;}return array;}}}/*** 単一始点最短経路問題と呼ぶらしい* verified - https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6293383#1*/class Dijkstra {static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();static long MAX = (long) 1e14;public Dijkstra(int N) {for (int i = 0; i < N; i++)graph.add(new ArrayList<>());}public void addEdge(int a, int b, long c) {graph.get(a).add(new Edge(b, c));}static long[] dijkstra(int v, int N) {long[] dist = new long[N];Arrays.fill(dist, MAX);dist[v] = 0;PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>((p1, p2) -> {if (p1.dist == p2.dist)return 0;return p1.dist - p2.dist < 0 ? -1 : 1;});pq.add(new Vertex(v, 0));while (!pq.isEmpty()) {Vertex now = pq.poll();int id = now.id;long d = now.dist;if (dist[id] < d)continue;for (Edge e : graph.get(id)) {int to = e.to;if (dist[to] > dist[id] + e.cost) {dist[to] = dist[id] + e.cost;pq.add(new Vertex(to, dist[to]));}}}return dist;}static class Edge {int to;long cost;public Edge(int to, long cost) {this.to = to;this.cost = cost;}}static class Vertex {int id;long dist;public Vertex(int id, long dist) {this.id = id;this.dist = dist;}}}/*** refercence : https://github.com/NASU41/AtCoderLibraryForJava/blob/master/ContestIO/ContestScanner.java*/class ContestScanner {private final java.io.InputStream in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private static final long LONG_MAX_TENTHS = 922337203685477580L;private static final int LONG_MAX_LAST_DIGIT = 7;private static final int LONG_MIN_LAST_DIGIT = 8;public ContestScanner(java.io.InputStream in){this.in = in;}public ContestScanner(java.io.File file) throws java.io.FileNotFoundException {this(new java.io.BufferedInputStream(new java.io.FileInputStream(file)));}public ContestScanner(){this(System.in);}private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (java.io.IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;return hasNextByte();}public String next() {if (!hasNext()) throw new java.util.NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) throw new java.util.NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {int digit = b - '0';if (n >= LONG_MAX_TENTHS) {if (n == LONG_MAX_TENTHS) {if (minus) {if (digit <= LONG_MIN_LAST_DIGIT) {n = -n * 10 - digit;b = readByte();if (!isPrintableChar(b)) {return n;} else if (b < '0' || '9' < b) {throw new NumberFormatException(String.format("%d%s... is not number", n, Character.toString(b)));}}} else {if (digit <= LONG_MAX_LAST_DIGIT) {n = n * 10 + digit;b = readByte();if (!isPrintableChar(b)) {return n;} else if (b < '0' || '9' < b) {throw new NumberFormatException(String.format("%d%s... is not number", n, Character.toString(b)));}}}}throw new ArithmeticException(String.format("%s%d%d... overflows long.", minus ? "-" : "", n, digit));}n = n * 10 + digit;}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public double nextDouble() {return Double.parseDouble(next());}public long[] nextLongArray(int length){long[] array = new long[length];for(int i=0; i<length; i++) array[i] = this.nextLong();return array;}public long[] nextLongArray(int length, java.util.function.LongUnaryOperator map){long[] array = new long[length];for(int i=0; i<length; i++) array[i] = map.applyAsLong(this.nextLong());return array;}public int[] nextIntArray(int length){int[] array = new int[length];for(int i=0; i<length; i++) array[i] = this.nextInt();return array;}public int[] nextIntArray(int length, java.util.function.IntUnaryOperator map){int[] array = new int[length];for(int i=0; i<length; i++) array[i] = map.applyAsInt(this.nextInt());return array;}public double[] nextDoubleArray(int length){double[] array = new double[length];for(int i=0; i<length; i++) array[i] = this.nextDouble();return array;}public double[] nextDoubleArray(int length, java.util.function.DoubleUnaryOperator map){double[] array = new double[length];for(int i=0; i<length; i++) array[i] = map.applyAsDouble(this.nextDouble());return array;}public long[][] nextLongMatrix(int height, int width){long[][] mat = new long[height][width];for(int h=0; h<height; h++) for(int w=0; w<width; w++){mat[h][w] = this.nextLong();}return mat;}public int[][] nextIntMatrix(int height, int width){int[][] mat = new int[height][width];for(int h=0; h<height; h++) for(int w=0; w<width; w++){mat[h][w] = this.nextInt();}return mat;}public double[][] nextDoubleMatrix(int height, int width){double[][] mat = new double[height][width];for(int h=0; h<height; h++) for(int w=0; w<width; w++){mat[h][w] = this.nextDouble();}return mat;}public char[][] nextCharMatrix(int height, int width){char[][] mat = new char[height][width];for(int h=0; h<height; h++){String s = this.next();for(int w=0; w<width; w++){mat[h][w] = s.charAt(w);}}return mat;}}