Submission #12498094

---

Source Code Expand

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

# Inputs

N,M,S = gets.split.map(&:to_i)
E = Array.new(N){ [] }
M.times.map{
	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{ 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<<18 | [s,4095].min<<6 | u
}
Я = lambda{|r|
	next r>>18, r>>6&4095, r&63
}

# Main

n,T,２ = 0, [nil]*N, [-1]*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

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

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

# Output

T.shift
p(*T)

__END__

こういう入力に弱い。

9 8 0
1 2 50 1
2 3 50 1
3 4 50 1
4 5 50 1
5 6 50 1
6 7 50 1
7 8 50 1
8 9 50 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

Submission Info

Judge Result