Submission #20371092

---

Source Code Expand

class PQ
	def initialize
		@h = [p] # min-heap, 1-indexed
	end

	def enq t,n
		@h << [t,n]
		up_heap
	end

	def deq
		if 1 < @h.size
			@h[1],@h[-1] = @h[-1],@h[1]
			t,n = @h.pop
			dn_heap
			return t,n
		end
	end

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

	def dn_heap
		i,sz1 = 1,@h.size-1
		while (iC = i+i) <= sz1
			iC += 1 if iC < sz1 && @h[iC+1][0] < @h[iC][0]
			break if @h[i][0] <= @h[iC][0]
			@h[i],@h[iC],i = @h[iC],@h[i],iC
		end
	end
end

(N,M,X,Y),*ABTK = $<.map{|ln| ln.split.map(&:to_i) }
Tr = ABTK.inject(Array.new(N+1){ [] }){|tr,(a,b,t,k)|
	tr[a] << [b,t,k]
	tr[b] << [a,t,k]
	next tr
}

T = [1.0/0]*(N+1)
Q = PQ.new
Q.enq 0,X
while (t0,n = Q.deq)
	next if T[n] < t0
	T[n] = t0
	break if n == Y

	Tr[n].each{|m,dt,k|
		t = (t0+k-1)/k*k+dt
		next if T[m] <= t
		T[m] = t
		Q.enq t,m
	}
end

p(T[Y].finite?? T[Y]:-1)

Submission Info

Judge Result