ABC211 D Number of Shortest paths
単に最短経路長であれば, ダイクストラ法を用いて高速に求められる. この問題は最短経路の個数を求める問題であるが, これについても通常のダイクストラ法に少し付け加えることで同様に求められる. 具体的には,
$ cnt_i
:= 頂点
$ i
までの最短経路の個数とおいて, 初めて訪れるか, そうでないかで場合分けしながら遷移することにより求められる.
実装例:
https://atcoder.jp/contests/abc211/submissions/24490808