結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-09-04 10:18:49
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 698 bytes
コンパイル時間 13,751 ms
コンパイル使用メモリ 315,108 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-04 10:19:04
合計ジャッジ時間 14,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

struct Road
  property s, t, y, m
  
  def initialize(@s : Int32, @t : Int32, @y : Int32, @m : Int32)
  end
end

n, c, v = read_line.split.map(&.to_i)
roads = [] of Road

v.times do
  s, t, y, m = read_line.split.map(&.to_i)
  roads << Road.new(s - 1, t - 1, y, m)
end

roads.sort_by! { |road| {road.s, road.t, road.y, road.m} }

dp = Array.new(n) { Array.new(c + 1, Int32::MAX) }
dp[0][0] = 0

roads.each do |road|
  (0..c).each do |i|
    if dp[road.s][i] != Int32::MAX && i + road.y <= c
      new_cost = dp[road.s][i] + road.m
      if new_cost < dp[road.t][i + road.y]
        dp[road.t][i + road.y] = new_cost
      end
    end
  end
end

ans = dp[n - 1].min
puts ans == Int32::MAX ? -1 : ans
0