Submission #32477294

---

Source Code Expand

class PQ
	def initialize
		@h = [] # min-heap
	end
 
	def enq c,a
		@h << [c,a]
		up_heap
	end
	def deq
		return unless @h[0]
		@h[0],@h[-1] = @h[-1],@h[0]
		c,a = @h.pop
		dn_heap if @h[0]
		return c,a
	end
 
private
	def up_heap
		c, = up = @h[i=@h.size-1]
		while 0<i
			iP = (i-1)/2
			break if @h[iP][0]<=c
			@h[i],i = @h[iP],iP
		end
		@h[i] = up
	end
	def dn_heap
		c, = dn = @h[i=0]
		z = @h.size
		until z <= iC = i+i+1
			iC += 1 if iC+1<z && @h[iC+1][0]<@h[iC][0]
			break if c<=@h[iC][0]
			@h[i],i = @h[iC],iC
		end
		@h[i] = dn
	end
end

(N,M),*ABCD = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N+1){[]}
ABCD.each{|a,b,c,d|
	next if a==b
	r = Integer.sqrt d
	E[a]<<[b,c,d,r+1]
	E[b]<<[a,c,d,r+1]
}

T = [1.0/0]*(N+1)
T[1] = 0
Q = PQ.new
Q.enq 0,1
while (t,a = Q.deq)
	next if T[a]<t
	E[a].each{|b,c,d,r|
		t1 = (t+2..[r,T[b]-c-d/r].min).bsearch{|t1| d.fdiv(t1)-d.fdiv(t1+1)<1 }||t+1
		t1 += c-1+d/t1
		Q.enq (T[b] = t1),b if t1<T[b]
	}
end

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

Submission Info

Judge Result