結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
![]() |
提出日時 | 2021-07-17 14:40:47 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 702 ms / 3,500 ms |
コード長 | 602 bytes |
コンパイル時間 | 11,229 ms |
コンパイル使用メモリ | 295,696 KB |
実行使用メモリ | 39,672 KB |
最終ジャッジ日時 | 2024-07-07 02:28:52 |
合計ジャッジ時間 | 20,490 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
n, m, k = read_line.split.map(&.to_i) g = Array.new(n) { [] of {Int32, Int32} } m.times do u, v, c = read_line.split.map(&.to_i.pred) g[u] << {v, c + 1} g[v] << {u, c + 1} end puts (0..2*10**5).bsearch { |x| que = Deque{0} dist = Array(Int32?).new(n, nil) dist[0] = 0 while v = que.shift? d = dist[v].not_nil! g[v].each do |u, c| cost = c > x ? 1 : 0 d2 = d + cost if (d3 = dist[u]).nil? || d2 < d3 dist[u] = d2 if cost == 0 que.unshift u else que.push u end end end end dist.last.not_nil! < k }