結果

問題 No.3263 違法な散歩道
ユーザー fumta
提出日時 2025-09-06 14:08:17
言語 Ruby
(3.4.1)
結果
AC  
実行時間 685 ms / 2,000 ms
コード長 668 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 7,808 KB
実行使用メモリ 34,616 KB
最終ジャッジ日時 2025-09-06 14:08:33
合計ジャッジ時間 13,986 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:34: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Syntax OK

ソースコード

diff #

require "set"

INF = 1 << 60
N, M = gets.split.map(&:to_i)
edges = Array.new(N) { [] }
M.times do |i|
  u, v = gets.split.map(&:to_i).map(&:pred)
  edges[u] << v
  edges[v] << u
end
K = gets.to_i
A = K.zero? ? [] : gets.split.map(&:to_i).map(&:pred).to_set

dists = Array.new(N) { Array.new(5, INF) }
dists[0][0] = 0

# [pos d, danger]
log = [[0, 0, 0 ]]
until log.empty?
  pos, d, danger = log.shift
  if pos == N - 1
    puts d
    exit
  end
  next if dists[pos][danger] < d
  edges[pos].each do |nxt|
    nd = A.include?(nxt) ? danger + 1 : 0
    next if nd >= 5 || dists[nxt][nd] <= d + 1
    dists[nxt][nd] = d + 1
    log << [nxt, d + 1, nd]
  end
end

puts -1
0