結果

問題 No.3263 違法な散歩道
ユーザー amesyu
提出日時 2025-09-06 13:49:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 413 ms / 2,000 ms
コード長 715 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 107,336 KB
最終ジャッジ日時 2025-09-06 13:49:33
合計ジャッジ時間 8,712 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

n, m = map(int, input().split())

g = [[] for _ in range(n)]
inf = int(1e9)
for _ in range(m):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    g[u].append(v)
    g[v].append(u)

k = int(input())
a = list(map(int, input().split())) if k else []
is_yiwiy = [0] * n
for v in a:
    is_yiwiy[v - 1] = 1
dp = [[inf] * 5 for _ in range(n)]
dp[0][0] = 0

q = deque([(0, 0)])
while q:
    x, c = q.popleft()

    for y in g[x]:
        nc = 0 if not is_yiwiy[y] else c + 1
        if nc >= 5:
            continue
        if dp[y][nc] != inf:
            continue
        dp[y][nc] = dp[x][c] + 1
        q.append((y, nc))

ans = min(dp[-1])
print(-1 if ans == inf else ans)
0