Submission #12489199

---

Source Code Expand

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

# Inputs

N,M,S = gets.split.map(&:to_i)
E,amax = Hash.new{|h,k| h[k]={} }, 0
M.times.map{
	u,v,a,b = gets.split.map(&:to_i)
	E[u-1][v-1] = E[v-1][u-1] = [a,b]
	amax = a if amax < a
}
X = N.times.map{ gets.split.map(&:to_i) }

# Tools

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

	def enq(v)
		@h.push(v)
		up_heap
	end

	def deq
		max, last = @h[0], @h.pop
		unless @h.empty?
			@h[0] = last
			dn_heap
		end
		return max
	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<<32 | [s,(N-1)*amax].min<<16 | u
}
Я = lambda{|r|
	next r>>32, r>>16&4095, r&63
}

# Main

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

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

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

	c,d = X[u]
	Q.enq R[t+d,s+c,u]

	E[u].each{|v,(a,b)|
		Q.enq R[t+b,s-a,v] if a<=s
	}
end

# Output

T.shift
p *T

Submission Info

Compile Error

./Main.rb:89: warning: `*' interpreted as argument prefix

Judge Result