結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 14:59:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 89,984 KB |
最終ジャッジ日時 | 2024-09-26 17:49:53 |
合計ジャッジ時間 | 10,394 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
############################################################# import sys sys.setrecursionlimit(10**7) from heapq import heappop,heappush from collections import deque,defaultdict,Counter from bisect import bisect_left, bisect_right from itertools import product,combinations,permutations from math import sin,cos #from math import isqrt #DO NOT USE PyPy ipt = sys.stdin.readline iin = lambda :int(ipt()) lmin = lambda :list(map(int,ipt().split())) INF = 1<<30 def bfs01(s,N,G): dq = deque() dq.append(s) cost = [INF]*N cost[s] = 0 while dq: cur = dq.pop() for nxt in G[cur]: if cost[nxt] != INF: continue cost[nxt] = cost[cur]+1 dq.appendleft(nxt) return cost ############################################################# N,M = lmin() G = [[] for _ in range(N)] for _ in range(M): a,b = lmin() G[a-1].append(b-1) cost1 = bfs01(0,N,G) cost2 = bfs01(N-2,N,G) cost3 = bfs01(N-1,N,G) ans = min(cost1[N-2]+cost2[N-1]+cost3[0],cost1[N-1]+cost3[N-2]+cost2[0]) if ans >= INF: print(-1) else: print(ans)