Submission #12916854

---

Source Code Expand

# 以下を参考にした：
# https://atcoder.jp/contests/abc164/submissions/12550661

# ツール

class PriorityQueue
	def initialize
		@heap = []
	end

	def push value
    @heap.push value
		update_heap_to_up
	end

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

  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

# 都市間の移動コストは最大50
# 都市は最大50なので、必要な最大コストは
# 50 * (50-1) = 2450
MAX_COST = 2450

def encode(time, money, city)
  (time << 18) | ([money, MAX_COST].min << 6) | city
end

def decode(value)
  # 4095 = 0b0000_1111_1111_1111 (12桁のマスク)
  #   63 = 0b0000_0000_0011_1111 ( 6桁のマスク)
  [(value >> 18), ((value >> 6) & 4095), (value & 63)]
end

# 入力

n, m, init_money = gets.split.map(&:to_i)

adj = n.times.map{Array.new}
m.times do
	from, to, money, time = gets.split.map(&:to_i)
  adj[from-1].push [to-1, money, time]
  adj[to-1].push [from-1, money, time]
end

exchange = n.times.map do
	money, time = gets.split.map(&:to_i)
	lambda do |current, target|
    need_count = (target - current + money - 1)/money # = ((target - current) / money.to_f).ceil
		[money * need_count, time * need_count]
  end
end

# メイン

reached = 0
min_time = Array.new(n, nil)  # 各都市に最初についた時間

max_money = Array.new(n, -1)  # 各都市で所持してた金額の最大値
need_money = Array.new(n, 0)  # 各都市で最低限必要となる金額
last_state = Array.new(n, nil)  # 各都市で最後に追加した状態

queue = PriorityQueue.new
queue.push encode(0, init_money, 0)

while state = queue.shift
	current_time, current_money, current_city = decode(state)

  # ループの後の方が時間が遅い（時間が早い順に処理してるため）
  # なので、かつて訪問していて所持金が以前の値以下の場合、
  # 結果が改善されることはないので探索をカットする
	next if current_money <= max_money[current_city]
	max_money[current_city] = current_money

	unless min_time[current_city] # 最初の訪問
		reached += 1
    min_time[current_city] = current_time
		break if reached == n # 完了
	end

	min_need_money = MAX_COST
	adj[current_city].each do |to_city, move_cost, move_time|
    # 移動後の所持金が以前の値以下だと意味がないので、
    # 以前の値より大きくなる場合だけノードを追加する
		if current_money - move_cost > max_money[to_city]
      next_money = current_money - move_cost
      next_time = current_time + move_time

      # 移動後に最低限必要となる金額未満でノードを登録すると両替が必要となるので、
      # 移動後に最低限必要な金額まであらかじめ両替しておく
      if next_money < need_money[to_city]
        exchange_money, exchange_time = exchange[to_city].call(next_money, need_money[to_city])
        next_money += exchange_money
        next_time += exchange_time
      end

      next_state = encode(next_time, next_money, to_city)
			if last_state[to_city] != next_state
				last_state[to_city] = next_state
				queue.push next_state
			end
		end

    # 現在の金額以下、もしくは(次の都市での所持金+移動コスト)以下でこの都市に来ても意味がない
    # すべての隣接都市に対しての下限を得る
    current_need_money = [current_money, max_money[to_city] + move_cost].max + 1
		min_need_money = [current_need_money, min_need_money].min
  end
	need_money[current_city] = min_need_money

  # 最低限必要な金額まで両替する
  exchange_money, exchange_time = exchange[current_city].call(current_money, min_need_money)
  next_state = encode(current_time + exchange_time, current_money + exchange_money, current_city)
	if last_state[current_city] != next_state
		last_state[current_city] = next_state
		queue.push next_state
	end
end

# 出力

min_time.shift
puts min_time.join("\n")

Submission Info

Judge Result