結果

問題 No.2565 はじめてのおつかい
ユーザー noriocnorioc
提出日時 2024-07-04 01:46:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 271 ms / 2,000 ms
コード長 771 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 95,940 KB
最終ジャッジ日時 2024-07-04 01:46:46
合計ジャッジ時間 13,012 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
55,312 KB
testcase_01 AC 43 ms
54,780 KB
testcase_02 AC 41 ms
55,284 KB
testcase_03 AC 199 ms
95,816 KB
testcase_04 AC 182 ms
95,940 KB
testcase_05 AC 42 ms
54,452 KB
testcase_06 AC 242 ms
81,076 KB
testcase_07 AC 142 ms
78,116 KB
testcase_08 AC 164 ms
80,576 KB
testcase_09 AC 196 ms
79,736 KB
testcase_10 AC 169 ms
80,928 KB
testcase_11 AC 263 ms
87,952 KB
testcase_12 AC 109 ms
77,296 KB
testcase_13 AC 182 ms
79,680 KB
testcase_14 AC 209 ms
84,264 KB
testcase_15 AC 215 ms
82,956 KB
testcase_16 AC 146 ms
89,632 KB
testcase_17 AC 88 ms
77,536 KB
testcase_18 AC 92 ms
80,412 KB
testcase_19 AC 236 ms
86,944 KB
testcase_20 AC 221 ms
86,500 KB
testcase_21 AC 194 ms
86,280 KB
testcase_22 AC 147 ms
82,468 KB
testcase_23 AC 161 ms
82,640 KB
testcase_24 AC 99 ms
77,136 KB
testcase_25 AC 232 ms
86,472 KB
testcase_26 AC 194 ms
82,272 KB
testcase_27 AC 196 ms
87,360 KB
testcase_28 AC 239 ms
86,632 KB
testcase_29 AC 271 ms
90,160 KB
testcase_30 AC 209 ms
88,272 KB
testcase_31 AC 230 ms
86,840 KB
testcase_32 AC 172 ms
82,196 KB
testcase_33 AC 223 ms
87,572 KB
testcase_34 AC 240 ms
83,972 KB
testcase_35 AC 179 ms
89,048 KB
testcase_36 AC 244 ms
86,344 KB
testcase_37 AC 178 ms
82,792 KB
testcase_38 AC 225 ms
85,128 KB
testcase_39 AC 232 ms
83,232 KB
testcase_40 AC 233 ms
88,476 KB
testcase_41 AC 255 ms
90,692 KB
testcase_42 AC 201 ms
81,736 KB
testcase_43 AC 215 ms
84,004 KB
testcase_44 AC 164 ms
80,352 KB
testcase_45 AC 123 ms
78,200 KB
testcase_46 AC 250 ms
83,292 KB
testcase_47 AC 167 ms
79,140 KB
testcase_48 AC 208 ms
80,060 KB
testcase_49 AC 113 ms
77,476 KB
testcase_50 AC 180 ms
79,280 KB
testcase_51 AC 41 ms
54,252 KB
testcase_52 AC 126 ms
77,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque

INF = 1 << 60
N, M = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append(v)


def calc(src: int) -> list:
    dists = [INF] * N
    dists[src] = 0
    q = deque([src])
    while q:
        v = q.popleft()
        for to in adj[v]:
            if dists[to] <= dists[v] + 1: continue
            dists[to] = dists[v] + 1
            q.append(to)

    return dists


def distance(src, dst) -> int:
    d = calc(src)
    return d[dst]


d1 = distance(0, N-2) + distance(N-2, N-1) + distance(N-1, 0)
d2 = distance(0, N-1) + distance(N-1, N-2) + distance(N-2, 0)
if d1 >= INF and d2 >= INF:
    print(-1)
    exit()

ans = min(d1, d2)
print(ans)
0