https://emtubasa.hateblo.jp/entry/2019/12/16/145819

解法

$s$ 、 $t$ それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。 $s$ から頂点 $i$ への最短距離を $ds_{i}$ , $t$ から頂点 $i$ の最短距離を $dt_{i}$ とします。また、 $s$ と $t$ の距離を $D$ とします。
頂点 $u,v$ に辺を張った際、仮に $s,u,v,t$ の順に頂点を通り、問題の条件を満たすとすると、

$ds_{u} + 1 + dt_{v} = D - 1$

となるはずです。
ということで、 $ds_{i} = x$ となる $i$ の個数を $x$ ごとに、同様に $dt_{j} = y$ となる $j$ の個数を $y$ ごとにあらかじめまとめておき、
$x + y = D - 2$ となるような $(x,y)$ のペアについて、それぞれの個数の積を計算し、その総和を求めれば答えとなります。
また、このとき、 $i,j$ が同じ頂点になることはありません(その際、 $ds_{i} + dt_{j} = D -1$ となり、これは $s$ から $t$ の最短距離が $D-1$ となってしまい、 $D$ が最短距離であることに矛盾します)。同様に、 $(i,j),(j,i)$ が重複して数えられることも似たような考えからありえません。