AOJ 2608 - Minus One
解法
、それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。から頂点への最短距離を,から頂点の最短距離をとします。また、との距離をとします。
頂点に辺を張った際、仮にの順に頂点を通り、問題の条件を満たすとすると、
となるはずです。
ということで、となるの個数をごとに、同様にとなるの個数をごとにあらかじめまとめておき、
となるようなのペアについて、それぞれの個数の積を計算し、その総和を求めれば答えとなります。
また、このとき、が同じ頂点になることはありません(その際、となり、これはからの最短距離がとなってしまい、が最短距離であることに矛盾します)。同様に、が重複して数えられることも似たような考えからありえません。