AtCoder Beginner Contest 211 D – Number of Shortest paths を解いた記録

問題の概要

\(N\)頂点\(M\)辺の重みなし無向グラフがある．各頂点には\(1\)から\(N\)までの番号がついている．
頂点\(1\)から\(N\)までの最短経路の本数を求め，\(10^{9}+7\)で割ったあまりを出力せよ．

問題へのリンク

制約

• \(1 \leq N, M \leq 2 \times 10^{5}\)
• 入力はすべて整数

解法

私がコンテスト中に用いた解法は，

頂点1から各頂点へ至る最短経路の長さだけを幅優先探索で求める
最短経路の長さの情報をもとに，最短経路の本数をメモ化再帰で求める


というものです．

頂点1から各頂点へ至る最短経路の長さを求めるパートは，幅優先探索をやるだけです．幅優先探索が分からない場合は，BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 – Qiitaなどをお読みいただければと思います．

問題は最短経路の本数をメモ化再帰で求めるパートです．
頂点\(1\)から頂点\(i\)までの最短経路の長さを\(cost[i]\)とし，頂点\(1\)から頂点\(i\)までの最短経路の本数を\(cnt[i]\)とします．
ここで，\(cost[1] = 0\), \(cnt[1] = 1\)と定めます．

\(cnt[i]\)は，頂点\(i\)に隣接している各頂点の\(cnt\)を見れば求められます．
頂点\(i\)までの最短経路の長さは\(cost[i]\)なので，最短経路で頂点\(i\)にたどり着くためには，
最短経路の長さが\(cost[i]-1\)となるような頂点へ最短経路でたどり着き，そこから頂点\(i\)へ移動する必要があります．
したがって，\(cnt[i]\)は頂点\(i\)に隣接している頂点のうち，\(cost\)が\(cost[i]-1\)であるような頂点の\(cnt\)の総和となります．

実装例