結果

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

ソースコード

diff # 

n = read_line.to_i
c = read_line.to_i
v = read_line.to_i

s = Array.new(v, 0)
t = Array.new(v, 0)
y = Array.new(v, 0)
m = Array.new(v, 0)

# Read the next 4 lines for S, T, Y, M
s_line = read_line.split.map(&.to_i)
t_line = read_line.split.map(&.to_i)
y_line = read_line.split.map(&.to_i)
m_line = read_line.split.map(&.to_i)

v.times do |i|
  s[i] = s_line[i] - 1
  t[i] = t_line[i] - 1
  y[i] = y_line[i]
  m[i] = m_line[i]
end

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

v.times do |i|
  graph[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
    graph[i].each do |to, cost, time|
      if k >= cost
        new_k = k - cost
        new_time = dp[i][k] + time
        if new_time < dp[to][new_k]
          dp[to][new_k] = new_time
        end
      end
    end
  end
end

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