結果

問題 No.3263 違法な散歩道
ユーザー fungsi
提出日時 2025-09-08 21:21:01
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 742 bytes
コンパイル時間 13,226 ms
コンパイル使用メモリ 310,664 KB
実行使用メモリ 20,216 KB
最終ジャッジ日時 2025-09-08 21:21:17
合計ジャッジ時間 16,598 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 2
other RE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = gets.not_nil!.split.map(&.to_i)
g = Array.new(n) { [] of Int32 }

m.times do
  u, v = gets.not_nil!.split.map(&.to_i)
  u -= 1
  v -= 1
  g[u] << v
  g[v] << u
end

flg = Array.new(n, false)
k = gets.not_nil!.to_i
k.times do
  x = gets.not_nil!.to_i
  x -= 1
  flg[x] = true
end

dist = Array.new(n) { Array.new(5, -1) }
dq = Deque(Tuple(Int32, Int32)).new
dist[0][0] = 0
dq.push({0, 0})

until dq.empty?
  u, c = dq.shift
  g[u].each do |v|
    nc = flg[v] ? c + 1 : 0
    if nc < 5 && dist[v][nc] == -1
      dist[v][nc] = dist[u][c] + 1
      dq.push({v, nc})
    end
  end
end

INF = 1_000_000_000
ans = INF
5.times do |i|
  if dist[n - 1][i] != -1
    ans = Math.min(ans, dist[n - 1][i])
  end
end

ans = -1 if ans == INF
puts ans
0