No.021 C

町 $a$ から他の町への最短距離をダイクストラ法で求める.

ある町 $c$ への最短距離が $n$ のとき, 町 $c$ への最短距離の組み合わせの数は, 町 $c$ に通じている町の中でその町への最短距離が $n-1$ である町への最短距離の組み合わせの数の和である.

あとは DP なり再帰なりで町 $b$ への最短距離の組み合わせの数を計算する.