結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー 学ぶマン
提出日時 2025-12-28 19:23:31
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 416 ms / 2,000 ms
コード長 1,018 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 332 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 107,428 KB
最終ジャッジ日時 2025-12-28 19:23:42
合計ジャッジ時間 10,420 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 10**10
from collections import deque
N, M = map(int, input().split())
G = [list() for _ in range(N + 1)]
for i in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

K = int(input())
iwai = [False]*(N + 1)
if K:
    A = list(map(int, input().split()))
    for a in A:
        iwai[a] = True

# 頂点拡張BFS
dist = [[INF] * (5) for _ in range(N + 1)]
# dist[pos][level]
dist[1][0] = 0
que = deque()
que.append((1, 0))
while que:
    pos, level = que.popleft()
    for nex in G[pos]:
        # nex は 岩井頂点なら、level を1つあげる
        # そうでないなら、0 にする
        if iwai[nex]:
            nexlevel = level + 1
        else:
            nexlevel = 0 
        # dist[nex][nexlevel] を短くできるならする
        if nexlevel != 5 and dist[nex][nexlevel] > dist[pos][level] + 1:
            dist[nex][nexlevel] = dist[pos][level] + 1
            que.append((nex, nexlevel))

ans = min(dist[-1])
if ans == INF:
    ans = -1
print(ans)
0