結果

問題 No.3263 違法な散歩道
ユーザー flippergo
提出日時 2025-09-07 16:02:45
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,027 bytes
コンパイル時間 540 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 319,212 KB
最終ジャッジ日時 2025-09-07 16:03:23
合計ジャッジ時間 38,679 ms
ジャッジサーバーID
（参考情報） 		judge / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 23 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
N,M = map(int,input().split())
G = {(i,j):[] for i in range(1,N+1) for j in range(5)}
for _ in range(M):
    u,v = map(int,input().split())
    for j in range(5):
        G[(u,j)].append((v,0))
        G[(v,j)].append((u,0))
        if j<4:
            G[(u,j)].append((v,j+1))
            G[(v,j)].append((u,j+1))
K = int(input())
A = list(map(int,input().split()))
B = [0]*(N+1)
for i in range(K):
    B[A[i]] = 1
INFTY = 10**6
dist = {(i,j):INFTY for i in range(1,N+1) for j in range(5)}
dist[(1,0)] = 0
que = [(0,(1,0))]  # (距離,頂点)
while que:
    d,x = heapq.heappop(que)
    v,j = x
    if dist[(v,j)]<d:continue
    for y,c in G[(v,j)]:
        if B[y]==1 and j<4 and c==j+1 and dist[(y,j+1)]>d+1:
            dist[(y,j+1)] = d+1
            heapq.heappush(que,(d+1,(y,j+1)))
        elif B[y]==0 and c==0 and dist[(y,0)]>d+1:
            dist[(y,0)] = d+1
            heapq.heappush(que,(d+1,(y,0)))
ans = min(dist[(N,j)] for j in range(5))
if ans>=INFTY:
    print(-1)
else:
    print(ans)
0