提出 #12550661

---

ソースコード 拡げる

# Studying https://img.atcoder.jp/abc164/editorial.pdf

# Inputs

N,M,S = gets.split.map(&:to_i)
E = Array.new(N){ [] }
M.times{
	u,v,a,b = gets.split.map(&:to_i)
	E[u-1] << [v-1,a,b]
	E[v-1] << [u-1,a,b]
}
X = N.times.map{
	c,d = gets.split.map(&:to_i)
	lambda{|＿,￣|
		x = (￣-＿+c-1)/c
		return c*x, d*x
	}
}

# Tools

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

	def enq v
		@h << v
		up_heap
	end

	def deq
		min, last = @h[0], @h.pop
		unless @h.empty?
			@h[0] = last
			dn_heap
		end
		return min
	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

R = lambda{|t,s,u|
	next t<<18 | [s,2450].min<<6 | u
}
Я = lambda{|r|
	next r>>18, r>>6&4095, r&63
}

# Main

n,T = 0, [nil]*N
２,３,４ = [-1]*N, [0]*N, [nil]*N
Q = PQ.new; Q.enq R[0,S,0]
while r = Q.deq
	t,s,u = Я[r]

	next if s <= ２[u] # 銭なしの再訪に用なし
	２[u] = s

	unless T[u] # first arrived.
		n, T[u] = n+1, t
		break if n == N # completed.
	end

	least_s = 2450
	E[u].each{|v,a,b|
		z, y = ２[v]+a, ３[v]+a # z < y
		if z < s
			c, d = s < y ? X[v][s-a,３[v]] : [0,0]
			if ４[v] != r = R[t+b+d,s-a+c,v]
				Q.enq(４[v] = r)
			end
		end
		least_s = [[s,z].max+1,least_s].min
	}
	３[u] = least_s

	c,d = X[u][s,least_s]
	if ４[u] != r = R[t+d,s+c,u]
		Q.enq(４[u] = r)
	end
end

# Output

T.shift
p(*T)

提出情報

ジャッジ結果