結果

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

ソースコード

diff # 

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

# Read all input at once
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)

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

v.times do |i|
  from = s_line[i] - 1
  to = t_line[i] - 1
  cost = y_line[i]
  time = m_line[i]
  graph[from] << {to, cost, time}
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|
    current_time = dp[i][k]
    next if current_time == INF
    
    graph[i].each do |to, cost, time|
      next if k < cost  # Early exit for insufficient coins
      
      new_k = k - cost
      new_time = current_time + time
      if new_time < dp[to][new_k]
        dp[to][new_k] = new_time
      end
    end
  end
end

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