結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー flippergo
提出日時 2025-09-07 16:10:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,018 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 250,196 KB
最終ジャッジ日時 2025-09-07 16:10:37
合計ジャッジ時間 33,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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())
B = [0]*(N+1)
if K>0:
    A = list(map(int,input().split()))
    for i in range(K):
        B[A[i]] = 1
INFTY = 10**6
dist = [[INFTY for _ in range(5)] for _ in range(N+1)]
dist[1][0] = 0
que = [(0,1,0)]  # (距離,頂点)
while que:
    d,v,j = heapq.heappop(que)
    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