結果

問題 No.2387 Yokan Factory
コンテスト
ユーザー ruthen71
提出日時 2023-07-21 23:32:34
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 3,307 bytes
コンパイル時間 85 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 42,016 KB
最終ジャッジ日時 2024-09-22 01:01:10
合計ジャッジ時間 8,198 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 1 -- * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:156: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Main.rb:116: warning: assigned but unused variable - i
Syntax OK

ソースコード

diff # 

# Priority Queue
# Reference: https://github.com/python/cpython/blob/main/Lib/heapq.py
class PriorityQueue
  # By default, the priority queue returns the maximum element first.
  # If a block is given, the priority between the elements is determined with it.
  # For example, the following block is given, the priority queue returns the minimum element first.
  # `PriorityQueue.new { |x, y| x < y }`
  #
  # A heap is an array for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.
  def initialize(array = [], &comp)
    @heap = array
    @comp = comp || proc { |x, y| x > y }
    heapify
  end

  def self.max(array)
    new(array)
  end

  def self.min(array)
    new(array){ |x, y| x < y }
  end

  def self.[](*array, &comp)
    new(array, &comp)
  end

  attr_reader :heap
  alias to_a heap

  # Push new element to the heap.
  def push(item)
    shift_down(0, @heap.push(item).size - 1)
    self
  end

  alias << push
  alias append push

  # Pop the element with the highest priority.
  def pop
    latest = @heap.pop
    return latest if empty?

    ret_item = heap[0]
    heap[0] = latest
    shift_up(0)
    ret_item
  end

  # Get the element with the highest priority.
  def get
    @heap[0]
  end

  alias top get
  alias first get

  # Returns true if the heap is empty.
  def empty?
    @heap.empty?
  end

  def size
    @heap.size
  end

  def to_s
    "<#{self.class}: @heap:(#{heap.join(', ')}), @comp:<#{@comp.class} #{@comp.source_location.join(':')}>>"
  end

  private

  def heapify
    (@heap.size / 2 - 1).downto(0) { |i| shift_up(i) }
  end

  def shift_up(pos)
    end_pos = @heap.size
    start_pos = pos
    new_item = @heap[pos]
    left_child_pos = 2 * pos + 1

    while left_child_pos < end_pos
      right_child_pos = left_child_pos + 1
      if right_child_pos < end_pos && @comp.call(@heap[right_child_pos], @heap[left_child_pos])
        left_child_pos = right_child_pos
      end
      # Move the higher priority child up.
      @heap[pos] = @heap[left_child_pos]
      pos = left_child_pos
      left_child_pos = 2 * pos + 1
    end
    @heap[pos] = new_item
    shift_down(start_pos, pos)
  end

  def shift_down(star_pos, pos)
    new_item = @heap[pos]
    while pos > star_pos
      parent_pos = (pos - 1) >> 1
      parent = @heap[parent_pos]
      break if @comp.call(parent, new_item)

      @heap[pos] = parent
      pos = parent_pos
    end
    @heap[pos] = new_item
  end
end

HeapQueue = PriorityQueue

N, M, X = gets.chomp.split(" ").map(&:to_i)
G = Array.new(N) { [] }
for i in 0..M - 1
  u, v, a, b = gets.chomp.split(" ").map(&:to_i);
  u = u - 1
  v = v - 1
  G[u] << [v, a, b]
  G[v] << [u, a, b]
end
INF = 2000000000000000000
solve = 0
ok, ng = 0, 1000000001
mask = (1 << 20) - 1
while ng - ok > 1
  md = (ok + ng) / 2
  dist = Array.new(N, INF)
  dist[0] = 0
  pq = PriorityQueue.new([0]) {|x, y| x < y}
  while !pq.empty?
    tmp = pq.pop
    d = tmp >> 20
    from = tmp & mask
    if d != dist[from]
      next
    end
    G[from].each do |to, c, w|
      if w >= md && dist[to] > dist[from] + c
        dist[to] = dist[from] + c
        pq.push((dist[to] << 20) + to)
      end
    end
  end
  if dist[N - 1] <= X
    ok = md
    solve = 1
  else
    ng = md
  end
end
if solve == 1
  puts ok
else
  puts -1
end
0