[競プロ典型90問 013] Passing

https://atcoder.jp/contests/typical90/tasks/typical90_m

ダイクストラ法をスタートとゴールの二カ所から進める問題。

解き方

街1から街kを経由して街Nまで移動するときにかかる時間の最小値を求めてください。

スタートからゴールならダイクストラ法でよさそうだが、「特定の街を経由」しないといけない制約に、初見だと頭を抱えてしまう。

これは解説によると、

• スタート地点 (1)
• ゴール地点 (N)

の二カ所から実行する。

と言われると同時に走査・探索するのは難しそうに思えるが、それぞれ別々のものとして順番に実行するだけでよい。

そして最後に「スタートから k」と「ゴールから k」までのコストを合計すれば k を経由した最小コストが求まる。

TLE 対策

普通に書くと一部のテストが 2 秒を超えて TLE になってしまうため、やむをえず、グラフと距離を配列で持つように工夫する。

コード (AC)

N, M = gets.split.collect(&:to_i)                     # => [7, 9]
ABC = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2, 2], [1, 3, 3], [2, 5, 2], [3, 4, 1], [3, 5, 4], [4, 7, 5], [5, 6, 1], [5, 7, 6], [6, 7, 3]]

START = 0                                             # => 0
GOAL  = N.pred                                        # => 6

G = Array.new(N) { [] }
ABC.each do |a, b, c|
  G[a.pred] << [b.pred, c]
  G[b.pred] << [a.pred, c]
end
G                                                     # => [[[1, 2], [2, 3]], [[0, 2], [4, 2]], [[0, 3], [3, 1], [4, 4]], [[2, 1], [6, 5]], [[1, 2], [2, 4], [5, 1], [6, 6]], [[4, 1], [6, 3]], [[3, 5], [4, 6], [5, 3]]]

def dijkstra_from(start)
  d = Array.new(N, Float::INFINITY) # distance
  d[start] = 0

  heap = Heap.new { |e| d[e] }
  heap << start

  until heap.empty?
    from = heap.pop
    G[from].each do |to, cost|
      v = d[from] + cost
      if v < d[to]
        d[to] = v
        heap << to
      end
    end
  end

  d
end

a = dijkstra_from(START)                              # => [0, 2, 3, 4, 4, 5, 8]
b = dijkstra_from(GOAL)                               # => [8, 6, 6, 5, 4, 3, 0]

ans = (START..GOAL).collect { |e| a[e] + b[e] }       # => [8, 8, 9, 9, 8, 8, 8]
puts ans