結果

問題 No.3263 違法な散歩道
ユーザー akebono03
提出日時 2025-09-06 14:05:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 952 ms / 2,000 ms
コード長 924 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 45,012 KB
最終ジャッジ日時 2025-09-06 14:06:16
合計ジャッジ時間 17,510 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

def ip():return int(input())
def mp():return map(int, input().split())
def lmp():return list(map(int, input().split()))
# 岩プロコン2 E No.3263 違法な散歩道
from collections import deque
N, M = mp()
edge = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(lambda x:int(x)-1, input().split())
  edge[u].append(v)
  edge[v].append(u)
K = ip()
A = list(map(lambda x:int(x)-1, input().split())) if K > 0 else []
I = [False] * N
for a in A:
  I[a] = True
que = deque()
que.append((0, 0))
INF = 10**6
dist = [[INF] * 5 for _ in range(N)]
dist[0][0] = 0
while que:
  v, c = que.popleft()
  for to in edge[v]:
    if I[to]:
      if c == 4:
        continue
      if dist[to][c+1] == INF:
        dist[to][c+1] = dist[v][c] + 1
        que.append((to, c+1))
    else:
      if dist[to][0] == INF:
        dist[to][0] = dist[v][c] + 1
        que.append((to, 0))
ans = min(dist[N-1])
print(-1 if ans == INF else ans)
0