結果
問題 | No.2565 はじめてのおつかい |
ユーザー | Asahi |
提出日時 | 2023-12-02 16:34:51 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 369 ms / 2,000 ms |
コード長 | 14,639 bytes |
コンパイル時間 | 3,606 ms |
コンパイル使用メモリ | 99,552 KB |
実行使用メモリ | 75,292 KB |
最終ジャッジ日時 | 2023-12-02 16:35:16 |
合計ジャッジ時間 | 16,575 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 104 ms
56,840 KB |
testcase_01 | AC | 101 ms
56,980 KB |
testcase_02 | AC | 101 ms
56,836 KB |
testcase_03 | AC | 369 ms
75,292 KB |
testcase_04 | AC | 297 ms
74,804 KB |
testcase_05 | AC | 117 ms
56,944 KB |
testcase_06 | AC | 261 ms
64,056 KB |
testcase_07 | AC | 226 ms
61,492 KB |
testcase_08 | AC | 198 ms
63,508 KB |
testcase_09 | AC | 257 ms
63,632 KB |
testcase_10 | AC | 208 ms
63,356 KB |
testcase_11 | AC | 267 ms
68,256 KB |
testcase_12 | AC | 203 ms
61,588 KB |
testcase_13 | AC | 219 ms
63,220 KB |
testcase_14 | AC | 257 ms
66,164 KB |
testcase_15 | AC | 257 ms
66,096 KB |
testcase_16 | AC | 174 ms
66,988 KB |
testcase_17 | AC | 125 ms
59,888 KB |
testcase_18 | AC | 172 ms
59,972 KB |
testcase_19 | AC | 252 ms
68,140 KB |
testcase_20 | AC | 246 ms
66,072 KB |
testcase_21 | AC | 223 ms
65,524 KB |
testcase_22 | AC | 173 ms
62,788 KB |
testcase_23 | AC | 195 ms
63,620 KB |
testcase_24 | AC | 152 ms
58,240 KB |
testcase_25 | AC | 298 ms
66,232 KB |
testcase_26 | AC | 201 ms
63,048 KB |
testcase_27 | AC | 217 ms
65,652 KB |
testcase_28 | AC | 268 ms
66,144 KB |
testcase_29 | AC | 268 ms
68,148 KB |
testcase_30 | AC | 228 ms
67,712 KB |
testcase_31 | AC | 239 ms
66,384 KB |
testcase_32 | AC | 195 ms
63,132 KB |
testcase_33 | AC | 229 ms
65,648 KB |
testcase_34 | AC | 259 ms
66,016 KB |
testcase_35 | AC | 237 ms
67,456 KB |
testcase_36 | AC | 248 ms
66,100 KB |
testcase_37 | AC | 202 ms
63,388 KB |
testcase_38 | AC | 235 ms
65,568 KB |
testcase_39 | AC | 263 ms
66,056 KB |
testcase_40 | AC | 254 ms
67,328 KB |
testcase_41 | AC | 259 ms
68,128 KB |
testcase_42 | AC | 213 ms
63,056 KB |
testcase_43 | AC | 244 ms
65,552 KB |
testcase_44 | AC | 196 ms
62,988 KB |
testcase_45 | AC | 178 ms
59,860 KB |
testcase_46 | AC | 273 ms
66,204 KB |
testcase_47 | AC | 273 ms
63,412 KB |
testcase_48 | AC | 203 ms
63,232 KB |
testcase_49 | AC | 193 ms
61,208 KB |
testcase_50 | AC | 321 ms
64,060 KB |
testcase_51 | AC | 114 ms
57,480 KB |
testcase_52 | AC | 208 ms
60,960 KB |
ソースコード
import java.util.*; import java.io.*; import java.math.*; import java.util.stream.*; import java.util.function.*; class Main implements Runnable { public void solve(){ int n = in.nextInt() , m = in.nextInt(); List<Integer> [] G = ArrayList(n); for(int i = 0 ; i < m ; i ++) { int u = in.nextInt() , v = in.nextInt(); --u;--v; G[u].add(v); } int [] case1 = bfs(0 , G); int [] case2 = bfs(n - 2, G); int [] case3 = bfs(n - 1, G); int p1 = case1[n - 1] + case3[n - 2] + case2[0] ; int p2 = case1[n - 2] + case2[n - 1] + case3[0] ; if(case1[n - 1] == inf || case3[n - 2] == inf || case2[0] == inf) { print(-1); return; } if(case1[n - 2] == inf || case2[n - 1] == inf || case3[0] == inf) { print(-1); return; } print(Math.min(p1,p2)); } int [] bfs(int start , List<Integer>[] G) { int [] dist = new int[G.length]; Arrays.fill(dist , inf); dist[start] = 0 ; Queue<Integer> Q = new ArrayDeque<>(); Q.add(start); while(!Q.isEmpty()) { int now = Q.poll(); for(int next : G[now]) { if(dist[next] < dist[now] + 1) continue; dist[next] = dist[now] + 1 ; Q.add(next); } } return dist; } public record Pair<T,S> (T fi , S se) { public String toString() { return "("+fi+","+se+")"; } } public record Trio<T,S,U>(T fi , S se , U th) { public String toString() { return "("+fi+","+se+","+th+")"; } } public PrintWriter out = new PrintWriter(System.out); public In in = new In(); public static final int mod7 = 1000000007; public static final int mod9 = 998244353; public static final int inf = (1 << 30); public static final long lnf = (1L << 60); public static final String yes = "Yes"; public static final String no = "No" ; public static final int [] dy4 = {-1,0,1,0}; public static final int [] dx4 = {0,1,0,-1}; public static final int [] dy8 = {-1,-1,-1,0,1,1,1,0}; public static final int [] dx8 = {-1,0,1,1,1,0,-1,-1}; public boolean isOver(int y , int x , int h , int w) { return y < 0 || x < 0 || y >= h || x >= w ; } public void swap(int [] array , int l , int r) { int tmp = array[l] ; array[l] = array[r] ; array[r] = tmp ; } public void swap(long [] array , int l , int r) { long tmp = array[l] ; array[l] = array[r] ; array[r] = tmp ; } public String swap(String string , int l , int r) { StringBuilder m = new StringBuilder(string) ; m.setCharAt(l, string.charAt(r)); m.setCharAt(r, string.charAt(l)); return m.toString(); } public String binarytoString(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; } public String binarytoString(long a , int len) { String b = Long.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; } public <T extends Comparable<T>> int LowCountClosed(List<T> A , T key) { return upperbound(A, key); } public <T extends Comparable<T>> int LowCountOpen(List<T> A , T key) { return lowerbound(A, key); } public <T extends Comparable<T>> int HighCountClosed(List<T> A , T key) { return A.size() - lowerbound(A, key); } public <T extends Comparable<T>> int HighCountOpen(List<T> A , T key) { return A.size() - upperbound(A, key); } // [) public <T extends Comparable<T>> int CountClosedOpen(List<T> A, T a, T b) { return lowerbound(A, b) - lowerbound(A, a); } // [] public <T extends Comparable<T>> int CountClosedClosed(List<T> A, T a, T b) { return upperbound(A, b) - lowerbound(A, a); } // (] public <T extends Comparable<T>> int CountOpenClosed(List<T> A, T a, T b) { return upperbound(A, b) - upperbound(A, a); } // () public <T extends Comparable<T>> int CountOpenOpen(List<T> A, T a, T b) { return lowerbound(A, b) - upperbound(A, a); } private <T extends Comparable<T>> int lowerbound(List<T> A, T key) { int left = 0 , right = A.size(); while (left < right) { int mid = (left + right) / 2; if (A.get(mid).compareTo(key) < 0) left = mid + 1; else right = mid; } return right; } private <T extends Comparable<T>> int upperbound(List<T> A, T key) { int left = 0 , right = A.size(); while (left < right) { int mid = (left + right) / 2; if (A.get(mid).compareTo(key) <= 0) left = mid + 1; else right = mid; } return right; } public Integer [] toInteger(int [] a) { return Arrays.stream(a).boxed().toArray(Integer[]::new); } public Long [] toLong(long [] a) { return Arrays.stream(a).boxed().toArray(Long[]::new); } public Double [] toDouble(double [] a) { return Arrays.stream(a).boxed().toArray(Double[]::new); } public int [] toIntArray(Collection<Integer> collection) { int [] array = new int[collection.size()]; int cur = 0 ; for(int value : collection) array[cur++] = value ; return array ; } public long [] toLongArray(Collection<Long> collection) { long [] array = new long[collection.size()]; int cur = 0 ; for(long value : collection) array[cur++] = value ; return array ; } public <T> List<T> ArrayList(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(ArrayList::new)); } public <T> HashSet<T> HashSet(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(HashSet::new)); } public <T> TreeSet<T> TreeSet(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(TreeSet::new)); } public <T> Deque<T> Deque(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(ArrayDeque::new)); } public <T> PriorityQueue<T> PriorityQueue(T [] a) { return Arrays.stream(a).collect(Collectors.toCollection(PriorityQueue::new)); } public <T> List <T> [] ArrayList(int n) { @SuppressWarnings("unchecked") List<T> [] G = new ArrayList[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayList<>(); return G ; } public <T> HashSet <T> [] HashSet(int n) { @SuppressWarnings("unchecked") HashSet<T> [] G = new HashSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new HashSet<>() ; return G ; } public <T> TreeSet <T> [] TreeSet(int n) { @SuppressWarnings("unchecked") TreeSet<T> [] G = new TreeSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeSet<>() ; return G ; } public <T> TreeSet <T> [] TreeSet(int n , Comparator<? super T> comparator) { @SuppressWarnings("unchecked") TreeSet<T> [] G = new TreeSet[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeSet<>(comparator) ; return G ; } public <T> Deque <T> [] Deque(int n) { @SuppressWarnings("unchecked") Deque<T> [] G = new ArrayDeque[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new ArrayDeque<>(); return G ; } public <T> PriorityQueue <T> [] PriorityQueue(int n) { @SuppressWarnings("unchecked") PriorityQueue<T> [] G = new PriorityQueue[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new PriorityQueue<>(); return G ; } public <T> PriorityQueue <T> [] PriorityQueue(int n , Comparator<? super T> comparator) { @SuppressWarnings("unchecked") PriorityQueue<T> [] G = new PriorityQueue[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new PriorityQueue<>(comparator); return G ; } public <K,V> HashMap <K,V> [] HashMap(int n) { @SuppressWarnings("unchecked") HashMap<K,V> [] G = new HashMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new HashMap<>() ; return G ; } public <K,V> TreeMap <K,V> [] TreeMap(int n) { @SuppressWarnings("unchecked") TreeMap<K,V> [] G = new TreeMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeMap<>() ; return G ; } public <K,V> TreeMap <K,V> [] TreeMap(int n , Comparator<? super K> comparator) { @SuppressWarnings("unchecked") TreeMap<K,V> [] G = new TreeMap[n]; for(int i = 0 ; i < n ; i ++ ) G[i] = new TreeMap<>(comparator) ; return G ; } //---------------------------------------------------------------------------------------// @SuppressWarnings("unchecked") public <T> void print(T ... data) { StringBuilder pr = new StringBuilder(); for(var temp : data) pr.append(temp+" "); out.println(pr.toString()); out.flush(); } public void print(String [][] array) { StringBuilder pr = new StringBuilder(); for(var temp : array) { for(var data : temp) { pr.append(data+" "); } pr.append("\n"); } if(0 < pr.length()) pr.deleteCharAt(pr.length() - 1); out.println(pr.toString()); out.flush(); } public void print(char [][] array) { StringBuilder pr = new StringBuilder(); for(var temp : array) { for(var data : temp) { pr.append(data); } pr.append("\n"); } if(0 < pr.length()) pr.deleteCharAt(pr.length() - 1); out.println(pr.toString()); out.flush(); } public <T> void print(Collection<T> collection) { StringBuilder pr = new StringBuilder(); for(T data : collection) pr.append(data +" "); out.println(pr.toString()); out.flush(); } public static void main(String ... args) { new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); } public void run() { solve(); out.flush(); } } class In { private final InputStream in = System.in; private final Scanner sc = new Scanner(System.in); private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (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; } private boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) { ptr++; } return hasNextByte(); } public String next() { if (!hasNext()) throw new 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 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') { n *= 10; n += b - '0'; }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 char nextChar() { return next().charAt(0); } public BigInteger nexBigInteger() { return sc.nextBigInteger(); } public int [] nextInt(int n) { int [] array = new int[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextInt(); } return array ; } public int [][] nextInt(int n , int m) { int [][] array = new int[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextInt(m); } return array ; } public long [] nextLong(int n) { long [] array = new long[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextLong(); } return array ; } public long [][] nextLong(int n , int m) { long [][] array = new long[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextLong(m); } return array ; } public double [] nextDouble(int n) { double [] array = new double[n]; for(int i = 0 ; i < n ; i ++) { array[i] = nextDouble(); } return array ; } public String [] next(int n) { String [] array = new String[n]; for(int i = 0 ; i < n ; i ++) { array[i] = next(); } return array ; } public String [][] next(int n , int m) { String [][] array = new String[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = next(m); } return array ; } public char [] nextChar(int n) { char [] array = new char[n]; String string = next() ; for(int i = 0 ; i < n ; i ++) { array[i] = string.charAt(i); } return array ; } public char [][] nextChar(int n , int m) { char [][] array = new char[n][m]; for(int i = 0 ; i < n ; i ++) { array[i] = nextChar(m); } return array ; } }