結果

問題 No.3263 違法な散歩道
ユーザー yuuDot
提出日時 2025-09-06 13:43:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 758 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 81,740 KB
実行使用メモリ 101,456 KB
最終ジャッジ日時 2025-09-06 13:43:28
合計ジャッジ時間 7,499 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque

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

k = int(input())
is_yiwiy9 = [False] * n
if k != 0:
    a = list(map(int, input().split()))
    for a_i in a:
        is_yiwiy9[a_i - 1] = True

vis = [[-1] * n for _ in range(5)]
que = deque()
vis[0][0] = 0
que.append((0, 0))
while que:
    ct, ci = que.popleft()
    if ci == n - 1:
        print(vis[ct][ci])
        exit()

    for ni in g[ci]:
        nt = ct + 1 if is_yiwiy9[ni] else 0
        if nt == 5:
            continue
        if vis[nt][ni] == -1:
            vis[nt][ni] = vis[ct][ci] + 1
            que.append((nt, ni))

print(-1)
0