結果

問題 No.3263 違法な散歩道
ユーザー かみのさちほ
提出日時 2025-09-07 20:34:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 389 ms / 2,000 ms
コード長 1,257 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 108,212 KB
最終ジャッジ日時 2025-09-07 20:34:56
合計ジャッジ時間 8,465 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

N, M = map(int, input().split())
graph = [[] for n in range(N + 1)]

for m in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

is_iwai = [False]*(N + 1)

K = int(input())

if K != 0:
    k_list = list(map(int, input().split()))

    for k in k_list:
        is_iwai[k] = True

used = [[10**9]*5 for n in range(N + 1)]

start = 1

queue = deque()

if is_iwai[start]:
    used[start][1] = 0
    queue.append((start, 0, 1))
else:
    used[start][0] = 0
    queue.append((start, 0, 0))

while queue:
    now = queue.popleft()
    now_p = now[0]
    now_l = now[1]
    now_i = now[2]
    # print(f"now_p:{now_p}")
    # print(f"now_l:{now_l}")
    # print(f"now_i:{now_i}")
    # used[now_p][now_i] = now_l
    neibors = graph[now_p]

    for neibor in neibors:
        iwai_count = now_i
        if is_iwai[neibor]:
            iwai_count += 1
        else:
            iwai_count = 0
        if iwai_count == 5:
            continue
        if used[neibor][iwai_count] != 10**9:
            continue
        queue.append((neibor, now_l + 1, iwai_count))
        used[neibor][iwai_count] = now_l + 1

# print(used)

if min(used[N]) == 10**9:
    print(-1)
else:
    print(min(used[N]))
0