結果

問題 No.3263 違法な散歩道
ユーザー detteiuu
提出日時 2025-09-06 13:20:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 451 ms / 2,000 ms
コード長 820 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 112,768 KB
最終ジャッジ日時 2025-09-06 13:21:06
合計ジャッジ時間 8,980 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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, v = u-1, v-1
    G[u].append(v)
    G[v].append(u)
K = int(input())
if K:
    A = list(map(int, input().split()))
else:
    A = []

INF = 1<<60

S = set()
for a in A:
    S.add(a-1)
visited = [[-1]*5 for _ in range(N)]
visited[0][0] = 0
que = deque()
que.append((0, 0))
while que:
    n, c = que.popleft()
    for v in G[n]:
        nc = c+1
        if v not in S:
            nc = 0
        if nc == 5:
            continue
        if visited[v][nc] == -1:
            visited[v][nc] = visited[n][c]+1
            que.append((v, nc))

ans = INF
for i in range(5):
    if visited[-1][i] != -1:
        ans = min(ans, visited[-1][i])

print(ans if ans != INF else -1)
0