結果

問題 No.3263 違法な散歩道
ユーザー flippergo
提出日時 2025-09-07 16:14:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,440 ms / 2,000 ms
コード長 999 bytes
コンパイル時間 546 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 227,664 KB
最終ジャッジ日時 2025-09-07 16:14:40
合計ジャッジ時間 21,390 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
N,M = map(int,input().split())
G = [[[] for _ in range(5)] for _ in range(N+1)]
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 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