結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:40:56 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 586 ms / 2,000 ms |
コード長 | 849 bytes |
コンパイル時間 | 70 ms |
コンパイル使用メモリ | 8,064 KB |
実行使用メモリ | 33,824 KB |
最終ジャッジ日時 | 2025-09-06 14:41:09 |
合計ジャッジ時間 | 12,462 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
Syntax OK
ソースコード
n, m = gets.split.map(&:to_i) g = Array.new(n) { Array.new() } m.times do u, v = gets.split.map(&:to_i) u -= 1 v -= 1 g[u] << v g[v] << u end k = gets.to_i a = [] if k > 0 then a = gets.split.map(&:to_i) end exist = Array.new(n, false) a.each do |i| exist[i - 1] = true end $MX = 1_000_000_000 dist = Array.new(n) { Array.new(5, $MX) } q = [] dist[0][0] = 0 q << [0, 0] while q.size > 0 v, x = q.shift g[v].each do |nv| nx = x if exist[nv] then nx += 1 else nx = 0 end if nx < 5 && dist[nv][nx] == $MX then dist[nv][nx] = dist[v][x] + 1 q << [nv, nx] end end end ans = $MX (0..4).each do |j| if ans > dist[n - 1][j] then ans = dist[n - 1][j] end end if ans == $MX then ans = -1 end puts ans