ABC 401-500/ABC413F - No Passage - 競技プログラミング用 知識集積所

---

問題

ABC413F

必要知識

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

別解