Submission #51749960

---

Source Code Expand

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

	def empty?
		@h.empty?
	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]
}

TX = 10**10
T = [nil]*(N+1)
T[1] = 0
que,que2 = PQ.new,PQ.new
que2.enq 0,1
until T[N]&.<TX || que2.empty?
	que,que2 = que2,que
	while (t,a = que.deq)
		next if T[a]<t
		T[a] = t
		E[a].each{|b,c|
			if c<0
				T[b] = TX and que2.enq t+1,b if ! T[b]
			else
				t1 = t<c ? c+1 : t+1
				T[b] = t1 and que.enq t1,b if ! T[b] || t1<T[b]
			end
		}
	end
end

p T[N]

Submission Info

Judge Result