Submission #51755608

---

Source Code Expand

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

	def head
		@h[0]
	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 = gets.split.map(&:to_i)
E = Array.new(N+1){[]}
M.times{
	a,b,c = gets.split.map(&:to_i)
	E[a]<<[b,c]
	E[b]<<[a,c]
}

U = 10**10
T = [U*N]*(N+1)
T[1] = 0
Q = PQ.new
Q.enq 0,1
while (t,a = Q.deq)
	E[a].each{|b,c|
		t1 = c<0 ? t+U+1 : t%U<c ? t-t%U+c+1 : t+1
		T[b] = t1 and Q.enq t1,b if t1<T[b]
	} if t==T[a]
end

p T[N]%U

Submission Info

Judge Result