結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー Yuto_kyopro0731
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0