提出 #61736134

---

ソースコード 拡げる

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













def dijkstra(graph, start, cost: ->(c, edge) { c + edge[1] })
    s = 1 << (graph.size - 1).bit_length
    dist = [Float::INFINITY] * graph.size
    none = [Float::INFINITY, nil]
    seg = [none] * (2 * s)
    update = ->(i, x) {
        i += s
        seg[i] = x
        while i > 1
            i >>= 1
            seg[i] = seg[i * 2, 2].min
        end
    }
    
    dist[start] = 0
    update.call(start, [0, start])

    until seg[1] == none
        current_dist, current_vertex = seg[1]
        update.call(current_vertex, none)
        
        next if current_dist > dist[current_vertex]
        
        graph[current_vertex].each do |edge|
            neighbor, _ = edge
            new_dist = cost.call(current_dist, edge)
            if dist[neighbor] > new_dist
                dist[neighbor] = new_dist
                update.call(neighbor, [new_dist, neighbor])
            end
        end
    end
    
    dist
end


main

提出情報

ジャッジ結果