結果

問題 No.3263 違法な散歩道
ユーザー sp8902zv
提出日時 2025-09-06 14:57:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 376 ms / 2,000 ms
コード長 835 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 107,276 KB
最終ジャッジ日時 2025-09-06 14:57:48
合計ジャッジ時間 7,760 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

import collections

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

A = [False] * N
K = int(input())
if K > 0:
    T = list(map(int, input().split()))
    for t in T:
        A[t-1] = True

inf = 10**18
visited = [[inf]*5 for _ in range(N)]
visited[0][0] = 0
que = collections.deque([(0, 0)])
while que:
    x, p = que.popleft()
    for nx in links[x]:
        if A[nx]:
            np = p + 1
        else:
            np = 0
            
        if np >= 5:
            continue
        
        if visited[nx][np] != inf:
            continue
        
        visited[nx][np] = visited[x][p] + 1
        que.append((nx, np))



ans = min(visited[N-1])
if ans == inf:
    ans = -1

print(ans)
0