競技プログラミング用 知識集積所

ABC429E - Hit and Away

最終更新:

sport_programming

- view
管理者のみ編集可


問題


必要知識

B以下レベルの内容は省略

考え方

問題で言っていることはつまり、各危険マスについて、最も近い安全地点と2番目に近い安全地点までの距離の和を出せということである。
よって、他始点の幅優先探索※を改造すればすぐ。

通常は最短距離を1つしか保管しないが、今回は
  • 最短距離がどのスタートから来たかを保管する(queue※の中にもスタート情報を入れる必要がある)
  • 次点候補が来た時に、最短と同じスタートだったら破棄し、違ったら記録する
という形に変えればよい。
あとは実装力勝負。

解答例


注意点


別解

タグ:

幅優先探索
ウィキ募集バナー