動的計画法しながら幅優先探索 AtCoder Beginner Contest 021 C - 正直者の高橋くん

問題

abc021.contest.atcoder.jp

あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町どうしを結ぶ M 本の道路が存在し、それらは双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。 また、M 個の道路はそれぞれ 道路 1,道路 2,…,道路 M と呼ばれています。

高橋君はあなたの家に遊びに行くことにしました。そして、高橋君は町 a から出発して、AtCoder 王国のいくつかの町（0 個でも良い）を経由して町 b にあるあなたの家に到着しました。

高橋君は最短経路を辿ってきたと主張しています。 高橋君は正直なので、絶対に嘘をつきません。

そこで、あなたは町 a から町 b への最短経路が何通りあるかを数えることにしました。答えは非常に大きくなる可能性があるので、実際の答えを 1,000,000,007(=109+7) で割った余りを出力してください。

町 a から町 b への最短経路とは、町 a から町 b への移動経路において道路を通る回数が最小となるような経路のことを言います。

note

幅優先して訪問しながら、その点まで何通り行く方法があるのか知りたいのでdpで求める。