Submission #61679977

---

Source Code Expand

def main
  n, m, x, y = gets.split.map(&:to_i)
  
  graph = Array.new(n) { [] }
  m.times do
    a, b, t, k = gets.split.map(&:to_i)
    graph[a - 1] << [b - 1, t, k]
    graph[b - 1] << [a - 1, t, k]
  end
  
  dist = dijkstra(graph, x - 1, cost:->(c, edge) { (c+edge[2]-1)/edge[2]*edge[2] + edge[1]}) 
  puts dist[y - 1] == Float::INFINITY ? -1 : dist[y - 1]
end













class MaxHeap
  def initialize
    @heap = []
  end

  def push(value)
    @heap << value
    heapify_up(@heap.size - 1)
  end

  def <<(value)
    push(value)
  end

  def peek
    @heap[0]
  end
  
  def empty?
    @heap.empty?
  end

  def pop
    return nil if @heap.empty?
    return @heap.pop if @heap.size == 1

    top = @heap[0]
    @heap[0] = @heap.pop
    heapify_down(0)
    top
  end

  private

  def heapify_up(child_index)
    return if child_index.zero?

    parent_index = (child_index - 1) / 2
    return if (@heap[parent_index] <=> @heap[child_index]) >= 0

    @heap[parent_index], @heap[child_index] = @heap[child_index], @heap[parent_index]
    heapify_up(parent_index)
  end

  def heapify_down(parent_index)
    left_child_index = parent_index * 2 + 1
    right_child_index = parent_index * 2 + 2
    largest = parent_index

    largest = left_child_index if left_child_index < @heap.size && (@heap[largest] <=> @heap[left_child_index])<0
    largest = right_child_index if right_child_index < @heap.size && (@heap[largest] <=> @heap[right_child_index])<0

    return if largest == parent_index

    @heap[parent_index], @heap[largest] = @heap[largest], @heap[parent_index]
    heapify_down(largest)
  end
end


def dijkstra(graph, start, cost: ->(c, edge) { c + edge[1] })
  dist = [Float::INFINITY] * graph.size
  dist[start] = 0

  heap = MaxHeap.new
  heap.push([-dist[start], start])
  until heap.empty?
    neg_d, current_vertex = heap.pop
    current_dist = -neg_d
    
    next if current_dist > dist[current_vertex]

    graph[current_vertex].each do |edge|
      neighbor, _ = edge
      new_dist  = cost.call(current_dist, edge)
      if new_dist < dist[neighbor]
        dist[neighbor] = new_dist
        heap.push([-new_dist, neighbor])
      end
    end
  end

  dist
end


main

Submission Info

Judge Result