結果
問題 | No.2565 はじめてのおつかい |
ユーザー | Kemty |
提出日時 | 2023-12-02 15:45:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 1,159 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 95,956 KB |
最終ジャッジ日時 | 2023-12-02 15:45:57 |
合計ジャッジ時間 | 10,700 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 92 ms
79,956 KB |
testcase_01 | AC | 91 ms
79,956 KB |
testcase_02 | AC | 93 ms
79,956 KB |
testcase_03 | AC | 243 ms
95,188 KB |
testcase_04 | AC | 164 ms
95,956 KB |
testcase_05 | AC | 91 ms
79,956 KB |
testcase_06 | AC | 168 ms
85,076 KB |
testcase_07 | AC | 134 ms
82,388 KB |
testcase_08 | AC | 154 ms
84,692 KB |
testcase_09 | AC | 155 ms
83,796 KB |
testcase_10 | AC | 146 ms
84,308 KB |
testcase_11 | AC | 230 ms
89,044 KB |
testcase_12 | AC | 118 ms
81,620 KB |
testcase_13 | AC | 161 ms
83,668 KB |
testcase_14 | AC | 188 ms
87,252 KB |
testcase_15 | AC | 185 ms
86,356 KB |
testcase_16 | AC | 155 ms
92,500 KB |
testcase_17 | AC | 107 ms
80,980 KB |
testcase_18 | AC | 111 ms
83,156 KB |
testcase_19 | AC | 217 ms
88,532 KB |
testcase_20 | AC | 197 ms
88,532 KB |
testcase_21 | AC | 170 ms
88,276 KB |
testcase_22 | AC | 150 ms
85,716 KB |
testcase_23 | AC | 168 ms
86,484 KB |
testcase_24 | AC | 113 ms
81,108 KB |
testcase_25 | AC | 205 ms
88,916 KB |
testcase_26 | AC | 160 ms
85,972 KB |
testcase_27 | AC | 153 ms
88,916 KB |
testcase_28 | AC | 196 ms
89,044 KB |
testcase_29 | AC | 208 ms
89,940 KB |
testcase_30 | AC | 177 ms
89,684 KB |
testcase_31 | AC | 198 ms
88,788 KB |
testcase_32 | AC | 162 ms
85,204 KB |
testcase_33 | AC | 176 ms
89,300 KB |
testcase_34 | AC | 197 ms
87,892 KB |
testcase_35 | AC | 160 ms
90,964 KB |
testcase_36 | AC | 221 ms
89,172 KB |
testcase_37 | AC | 178 ms
86,100 KB |
testcase_38 | AC | 174 ms
87,380 KB |
testcase_39 | AC | 189 ms
85,972 KB |
testcase_40 | AC | 183 ms
90,324 KB |
testcase_41 | AC | 187 ms
90,580 KB |
testcase_42 | AC | 160 ms
84,820 KB |
testcase_43 | AC | 164 ms
86,740 KB |
testcase_44 | AC | 157 ms
84,052 KB |
testcase_45 | AC | 133 ms
82,644 KB |
testcase_46 | AC | 172 ms
86,996 KB |
testcase_47 | AC | 138 ms
83,156 KB |
testcase_48 | AC | 160 ms
84,692 KB |
testcase_49 | AC | 125 ms
81,748 KB |
testcase_50 | AC | 146 ms
83,028 KB |
testcase_51 | AC | 89 ms
79,956 KB |
testcase_52 | AC | 116 ms
81,620 KB |
ソースコード
from collections import defaultdict, deque, Counter import copy from itertools import combinations, permutations, product, accumulate, groupby, chain from heapq import heapify, heappop, heappush import math import bisect from pprint import pprint from random import randint import sys # sys.setrecursionlimit(700000) input = lambda: sys.stdin.readline().rstrip('\n') inf = float('inf') mod1 = 10**9+7 mod2 = 998244353 def ceil_div(x, y): return -(-x//y) ################################################ def bfs(s, t): dist = [-1]*N dq = deque([s]) dist[s] = 0 while dq: now = dq.pop() for nxt in adj[now]: if dist[nxt] == -1: dist[nxt] = dist[now]+1 if nxt == t: return dist[t] dq.appendleft(nxt) return inf N, M = map(int, input().split()) adj = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u -= 1; v -= 1 adj[u].append(v) d1 = 0 d1 += bfs(0, N-2) d1 += bfs(N-2, N-1) d1 += bfs(N-1, 0) d2 = 0 d2 += bfs(0, N-1) d2 += bfs(N-1, N-2) d2 += bfs(N-2, 0) print(min(d1, d2) if min(d1, d2) != inf else -1)