結果

問題 No.1 道のショートカット
コンテスト
ユーザー vjudge1
提出日時 2025-09-04 10:22:43
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 777 bytes
コンパイル時間 12,984 ms
コンパイル使用メモリ 314,508 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-04 10:22:58
合計ジャッジ時間 14,704 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3 RE * 1
other AC * 2 WA * 2 RE * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# Read n, c, v
n = read_line.to_i
c = read_line.to_i
v = read_line.to_i

roads = [] of Road

v.times do
  data = read_line.split.map(&.to_i)
  if data.size == 4
    s, t, y, m = data
    roads << Road.new(s - 1, t - 1, y, m)
  end
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