Submission #13001464

---

Source Code Expand

class PriorityQueue
  def initialize
    @h = [] # min-heap
  end

  def enq v
    @h << v
    up_heap
  end
  alias :push :enq

  def deq
    min, last = @h[0], @h.pop
    unless @h.empty?
      @h[0] = last
      dn_heap
    end
    return min
  end
  alias :pop :deq

  def empty?
    @h.empty?
  end

  private
  def up_heap
    i, up = @h.size-1, @h[-1]
    while 0 <= (iP = (i-1)/2)
      break unless up < @h[iP]
      @h[i], i = @h[iP], iP
    end
    @h[i] = up
  end

  def dn_heap
    i, dn, size = 0, @h[0], @h.size
    while (iC = 2*i+1) < size
      iC += 1 if iC+1 < size and @h[iC+1] < @h[iC]
      break unless @h[iC] < dn
      @h[i], i = @h[iC], iC
    end
    @h[i] = dn
  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

# プライオリティキューのライブラリを利用
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