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

ABC413F - No Passage

最終更新:

sport_programming

- view
管理者のみ編集可


問題


必要知識

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

考え方

通常の幅優先探索(未作成)と比べて、「最短ルートではなく2番目に近いルートに進むことになる」だけ。
つまり、幅優先探索(未作成)のコードのそのあたりの部分を書き換えるだけ。

解答例


注意点

解答にはlong long型を用いる。

最終的な値はint型をはみ出る場合がある。
例えば以下のような場合、マスの中にHWの半分くらいの値まで入るので、答えがだいたい(1/2)(HW)^2くらいになる可能性がある。
1 G G G G G
G 1 2 3 4 5
11 10 9 8 7 6
12 11 10 9 8 G
13 14 15 16 17 18
G 15 16 17 18 19


別解

タグ:

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