結果
問題 | No.416 旅行会社 |
ユーザー |
![]() |
提出日時 | 2022-02-18 02:28:58 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 1,685 ms / 4,000 ms |
コード長 | 742 bytes |
コンパイル時間 | 405 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 62,336 KB |
最終ジャッジ日時 | 2024-12-14 21:15:10 |
合計ジャッジ時間 | 18,936 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
Syntax OK
ソースコード
N, M, Q = gets.split.map(&:to_i)E = Hash.new { |h, k| h[k] = Hash.new(false) }C = M.times.map { gets.split.map(&:to_i) }D = Q.times.map { gets.split.map(&:to_i) }C.each do |a, b|E[a][b] = E[b][a] = trueendD.each do |a, b|E[a][b] = E[b][a] = falseendV = Array.new(N + 1, nil)def bfs(root, t)queue = []queue << rootuntil queue.empty?v = queue.shiftnext if V[v]V[v] = tE[v].each do |u, s|next if not squeue << uendendendbfs(1, 0)D.reverse_each.with_index(1) do |(a, b), t|E[a][b] = E[b][a] = trueif V[a] && V[b].nil?bfs(b, t)endif V[b] && V[a].nil?bfs(a, t)endendputs (2..N).map { |x| t = Q - (V[x] || Q + 1) + 1; t == Q + 1 ? -1 : t }