結果

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

ソースコード

diff # 

n, c, v = read_line.split.map(&.to_i)
s = read_line.split.map(&.to_i)
t = read_line.split.map(&.to_i)
y = read_line.split.map(&.to_i)
m = read_line.split.map(&.to_i)

# Convert to 0-based indexing
s.map! { |x| x - 1 }
t.map! { |x| x - 1 }

edges = Array.new(n) { [] of Tuple(Int32, Int32, Int32) }
v.times do |i|
  edges[s[i]] << {t[i], y[i], m[i]}
end

INF = 1_000_000_000
dp = Array.new(n) { Array.new(c + 1, INF) }
dp[0][c] = 0

n.times do |i|
  c.downto(0) do |k|
    next if dp[i][k] == INF
    edges[i].each do |to, cost, time|
      next if k < cost
      new_k = k - cost
      new_time = dp[i][k] + time
      dp[to][new_k] = new_time if new_time < dp[to][new_k]
    end
  end
end

min_time = dp[n - 1].min
puts min_time == INF ? -1 : min_time
0