結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー yas_yasyu
提出日時 2025-09-06 14:40:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 374 ms / 2,000 ms
コード長 995 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 82,800 KB
実行使用メモリ 106,496 KB
最終ジャッジ日時 2025-09-06 14:40:24
合計ジャッジ時間 8,631 ms
ジャッジサーバーID
（参考情報） 		judge / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque


N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    graph[u].append(v)
    graph[v].append(u)

K = int(input())
if K > 0:
    exist_yiwiy9 = set(map(lambda x: int(x) - 1, input().split()))
else:
    exist_yiwiy9 = set()

INF = 10**20

dist = [[INF] * N for _ in range(5)]
dist[0][0] = 0
que = deque([(0, 0)])
while que:
    cur_yiwiy9, cur = que.popleft()
    for nxt in graph[cur]:
        nxt_yiwiy9 = cur_yiwiy9
        if nxt in exist_yiwiy9:
            nxt_yiwiy9 += 1
            if nxt_yiwiy9 >= 5:
                continue

        else:
            nxt_yiwiy9 = 0
        if dist[nxt_yiwiy9][nxt] <= dist[cur_yiwiy9][cur] + 1:
            continue

        dist[nxt_yiwiy9][nxt] = dist[cur_yiwiy9][cur] + 1
        que.append((nxt_yiwiy9, nxt))
# print(*dist, sep="\n")
ans = min(dist[cnt_yiwiy9][N - 1] for cnt_yiwiy9 in range(5))
print(ans if ans < INF else -1)
0