Submission #19432995

---

Source Code Expand

class Heap
  def initialize(&block)
    @a = []
    @f = block
  end

  def push t
    n = @a.size
    @a << t
    
    while n > 0
      i = (n-1) / 2
      @a[n], @a[i] = @a[i], @a[n] if @f[@a[n], @a[i]]
      n = i
    end
  end

  def shift
    n = @a.size - 1
    if n < 1
      @a.pop
    else
      r, @a[0], i = @a[0], @a.pop, 0
      while (j = 2 * i + 1) < n
        j += 1 if j != n - 1 && @f[@a[j+1], @a[j]]
        @a[i], @a[j] = @a[j], @a[i] if @f[@a[j], @a[i]]
        i = j
      end
      r
    end
  end
end

N, M = gets.split.map(&:to_i)
E = Array.new(N) {[]}
M.times do
  f, t, c = gets.split.map(&:to_i)
  E[f] << [t, c]
  E[t] << [f, c]
end

f =-> m {
  c = Array.new(N) {Array.new(m)}
  h = Heap.new {|x,y| x[1] < y[1]}
  h.push [0,0]
  while (i,s = h.shift)
    c[i][s % m] ||= (
      E[i].each {h.push [_1, _2 + s]}if i < N - 1
      s
    )
  end
  c
}
p [f[4][-1][0], f[7][-1][0]].compact.min

Submission Info

Judge Result