結果

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

ソースコード

diff # 

n, c, v = gets.as(String).split.map(&.to_i)
s = Array.new(v) { gets.as(String).split.map(&.to_i)[0] - 1 }
t = Array.new(v) { gets.as(String).split.map(&.to_i)[0] - 1 }
y = Array.new(v) { gets.as(String).split.map(&.to_i)[0] }
m = Array.new(v) { gets.as(String).split.map(&.to_i)[0] }

graph = Array.new(n) { [] of Tuple(Int32, Int32, Int32) }

v.times do |i|
  graph[s[i]] << {t[i], y[i], m[i]}
end

INF = 10**9
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
    
    graph[i].each do |to, cost, time|
      next if k < cost
      dp[to][k - cost] = Math.min(dp[to][k - cost], dp[i][k] + time)
    end
  end
end

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