結果

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

ソースコード

diff # 

struct Edge
  property target : Int32
  property cost : Int32
  property time : Int32
  
  def initialize(@target, @cost, @time)
  end
end

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

v.times do |i|
  s[i] = read_line.to_i - 1
end

v.times do |i|
  t[i] = read_line.to_i - 1
end

v.times do |i|
  y[i] = read_line.to_i
end

v.times do |i|
  m[i] = read_line.to_i
end

# Build adjacency list
graph = Array(Array(Edge)).new(n) { [] of Edge }
v.times do |i|
  graph[s[i]] << Edge.new(t[i], y[i], m[i])
end

# Priority queues for each node (cost, time)
vq = Array(Set({Int32, Int32})).new(n) { Set({Int32, Int32}).new }
vq[0] << {0, 0}

n.times do |i|
  min_time = Int32::MAX
  vq[i].each do |(cost, time)|
    next if min_time <= time
    min_time = time
    
    graph[i].each do |edge|
      new_cost = cost + edge.cost
      new_time = time + edge.time
      
      if new_cost <= c
        vq[edge.target] << {new_cost, new_time}
      end
    end
  end
end

minv = Int32::MAX
vq[n - 1].each do |(cost, time)|
  minv = Math.min(minv, time)
end

minv = -1 if minv == Int32::MAX
puts minv
0