ABC021 C - 正直者の高橋くん
問題
提出コード
辺被りを考慮しないコードも提出してみたのですが、どうやらないらしいです
解法
cnt[i] = i番目の町へ行く最短経路の数(で割った余りをとります)
とすると、cnt[b]が答えになります。初期値は、cnt[a]=1です。
あとは、aから幅優先探索をしていけば答えが求まります。
最短距離を記録しておき、今xからyへ向かったとします。
aからyへの最短距離が、xの最短距離+1と等しければ、cnt[y]にcnt[x]を加算していきます。
これを繰り返し、キューの中が空になるまで行えば、答えが求まります。
ある頂点をキューに入れる操作を、間違えて2回以上行わないこと、そしてで割った余りを取り忘れないようにすることを特に注意しましょう。