結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー norioc
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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