#1175576 (Ruby) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:26:41
• 言語: Ruby (4.0.6)
• 結果: AC
• 実行時間: 2,239 ms / 3,000 ms
• コード長: 4,116 bytes
• コンパイル時間: 435 ms
• コンパイル使用メモリ: 8,704 KB
• 実行使用メモリ: 46,848 KB
• 最終ジャッジ日時: 2026-09-04 22:11:56
• 合計ジャッジ時間: 27,628 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 30

コンパイルメッセージ

Syntax OK

ソースコード

MAX_AB = 300

class FastScanner
  def initialize
    @input = STDIN.read
    @index = 0
    @length = @input.length
  end

  def next_int
    input = @input
    index = @index
    length = @length

    while index < length && input.getbyte(index) <= 32
      index += 1
    end

    sign = 1

    if input.getbyte(index) == 45
      sign = -1
      index += 1
    end

    value = 0

    while index < length
      c = input.getbyte(index)
      break if c <= 32

      value = value * 10 + c - 48
      index += 1
    end

    @index = index
    value * sign
  end
end

# 状態aのほうが状態bより優先されるかを判定する。
# 距離が小さいものを優先し、距離が等しければ頂点番号が小さいものを優先する。
def state_less?(a, b)
  a[0] < b[0] || (a[0] == b[0] && a[1] < b[1])
end

def heap_push(heap, item)
  index = heap.length
  heap << item

  while index > 0
    parent = (index - 1) / 2

    break unless state_less?(item, heap[parent])

    heap[index] = heap[parent]
    index = parent
  end

  heap[index] = item
end

def heap_pop(heap)
  root = heap[0]
  last = heap.pop

  return root if heap.empty?

  index = 0
  length = heap.length

  while (left = index * 2 + 1) < length
    right = left + 1

    child =
      if right < length && state_less?(heap[right], heap[left])
        right
      else
        left
      end

    break unless state_less?(heap[child], last)

    heap[index] = heap[child]
    index = child
  end

  heap[index] = last
  root
end

scanner = FastScanner.new

n = scanner.next_int
m = scanner.next_int

raw_edges = Array.new(m)

# maximum_exponent[p]は、いずれかのb_iに現れる
# 素数pの指数の最大値。
maximum_exponent = Array.new(MAX_AB + 1, 0)

m.times do |i|
  u = scanner.next_int - 1
  v = scanner.next_int - 1
  a = scanner.next_int
  b = scanner.next_int

  raw_edges[i] = [u, v, a, b]

  value = b
  prime = 2

  while prime * prime <= value
    if value % prime != 0
      prime += 1
      next
    end

    exponent = 0

    while value % prime == 0
      value /= prime
      exponent += 1
    end

    maximum_exponent[prime] =
      [maximum_exponent[prime], exponent].max

    prime += 1
  end

  if value > 1
    maximum_exponent[value] =
      [maximum_exponent[value], 1].max
  end
end

# すべてのb_iを割り切る共通分母を構築する。
common_denominator = 1
prime_powers = []

(2..MAX_AB).each do |prime|
  exponent = maximum_exponent[prime]

  next if exponent == 0

  prime_powers << [prime, exponent]

  exponent.times do
    common_denominator *= prime
  end
end

graph = Array.new(n) { [] }

raw_edges.each do |raw|
  u, v, numerator, denominator = raw

  scaled_weight =
    common_denominator / denominator * numerator

  # RubyのIntegerは不変なので、同じ値を両方向で共有できる。
  graph[u] << [v, scaled_weight]
  graph[v] << [u, scaled_weight]
end

distance = Array.new(n)
reached = Array.new(n, false)

# [距離, 頂点番号]を格納する最小ヒープ。
queue = []

reached[0] = true
distance[0] = 0
heap_push(queue, [0, 0])

until queue.empty?
  current_distance, current_vertex = heap_pop(queue)

  if !reached[current_vertex] ||
     current_distance != distance[current_vertex]
    next
  end

  graph[current_vertex].each do |edge|
    to, weight = edge

    # 任意精度整数の加算を一度だけ行う。
    next_distance = current_distance + weight

    if !reached[to] || next_distance < distance[to]
      reached[to] = true
      distance[to] = next_distance
      heap_push(queue, [next_distance, to])
    end
  end
end

output = String.new

(1...n).each do |vertex|
  numerator = distance[vertex]
  denominator = common_denominator

  # 分母の素因数分解は既知なので、
  # 各素数で割れる回数だけ約分する。
  prime_powers.each do |prime, exponent|
    exponent.times do
      break if numerator % prime != 0

      numerator /= prime
      denominator /= prime
    end
  end

  output << numerator.to_s
  output << ' '
  output << denominator.to_s
  output << "\n"
end

STDOUT.write(output)