Submission #13001205

---

Source Code Expand

class PriorityQueue
  def initialize
    @heap = []
  end

  def push value
    @heap.push value
    update_heap_to_up
  end

  def empty?
    @heap.empty?
  end

  def shift
    min, last = @heap[0], @heap.pop
    unless @heap.empty?
      @heap[0] = last
      update_heap_to_down
    end
    min
  end

  alias pop shift

  private

  def update_heap_to_up
    index    = @heap.size - 1
    up_value = @heap[index]
    while 0 <= (parent_index = (index - 1) / 2)
      parent_value = @heap[parent_index]
      break if parent_value <= up_value

      @heap[index] = parent_value
      index        = parent_index
    end
    @heap[index] = up_value
  end

  def update_heap_to_down
    index      = 0
    down_value = @heap[0]
    size       = @heap.size
    while (child_index = 2 * index + 1) < size
      # 右の子がいて、右の子が小さければ、右の子を使う
      child_index += 1 if child_index + 1 < size and @heap[child_index + 1] < @heap[child_index]
      child_value = @heap[child_index]
      break if down_value <= child_value

      @heap[index] = child_value
      index        = child_index
    end
    @heap[index] = down_value
  end
end

MAX_V = 50 # 制約の最大値。
MAX_S = MAX_V * 50 + 5
INF   = Float::INFINITY

#　頂点
Edge = Struct.new(:to, :a, :b)
#　両替所
Exchange = Struct.new(:v, :s, :x) do
  include Comparable
  def <=>(other)
    self.x <=> other.x
  end
end

g    = Array.new(MAX_V) { Array.new { Edge.new } }
dist = Array.new(MAX_V) { Array.new(MAX_S + 5) { INF } }

def input
  gets.split.map &:to_i;
end

# メイン
n, m, s = input
#　都市の入力
m.times do
  u, v, a, b = input
  u          = u.pred
  v          = v.pred
  g[u] << Edge.new(v, a, b)
  g[v] << Edge.new(u, a, b)
end

# プライオリティキューのライブラリを利用
# require 'pqueue'
# 銀貨は最大でもMAX_S
s = [s, MAX_S].min
# プライオリティーキュー
q = PriorityQueue.new
# 入力用ラムダ
push = lambda { |v, s, x|
  return if s < 0
  return if dist[v][s] <= x

  dist[v][s] = x
  q.push(Exchange.new(v, s, x))
}

c = []
d = []
n.times do |i|
  cc, dd = input
  c[i]   = cc
  d[i]   = dd
end
push.call(0, s, 0)
until q.empty?
  hoge = q.pop
  v    = hoge.v; s = hoge.s; x = hoge.x
  next if dist[v][s] != x

  ns = [s + c[v], MAX_S].min
  push.call(v, ns, x + d[v])

  g[v].each do |e|
    push.call(e.to, s - e.a, x + e.b)
  end
end


(1 ... n).each do |i|
  ans = INF
  (0 ... (MAX_S + 5)).each do |j|
    ans = [ans, dist[i][j]].min
  end
  puts ans
end

Submission Info

Judge Result