結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 17:00:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,498 bytes |
コンパイル時間 | 358 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 102,016 KB |
最終ジャッジ日時 | 2024-09-26 21:02:17 |
合計ジャッジ時間 | 4,675 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | TLE * 1 -- * 49 |
ソースコード
from collections import deque from heapq import* INF = 10**6 N,M = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): u,v = map(int, input().split()) G[u-1].append(v-1) for i in range(N):G[i].sort() # 幅優先探索を行う deq = deque([]) # 探索予定の頂点を入れるデック seen = [False for _ in range(N)] # seen[v]:頂点 v が探索済みなら true, そうでないなら false s = N-2 # 頂点 s を始点として登録する deq.append(s) seen[s] = True # デックの中身が空になるまで while len(deq) > 0: # これから探索する頂点を v とする v = deq.popleft() # 頂点 v からたどれる頂点 v2 について for v2 in G[v]: # すでに探索済みなら、スキップ if seen[v2]: continue # そうでないなら、デックに入れて訪問済みにする deq.append(v2) seen[v2] = True # 頂点 t を訪問済みかど def calc(i): q = [(0,i)] L = [INF]*N L[i] = 0 k = [0]*N while q: c0,p = heappop(q) if k[p]:continue k[p] = 1 for v in range(N): nc = c0+1 if L[v] > nc: L[v] = nc heappush(q,(nc,v)) return L depthN = calc(0) depth0N = calc(N-1) depth0N_1 =calc(N-2) if seen[N-1]: if depthN[N-1] < depthN[N-2]: print(depthN[N-1]+depth0N[0]) else: print(depthN[N-2] + depth0N_1[0]) else: print(-1)