ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2608 - Minus One

問題
提出コード

解法

stそれぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。sから頂点iへの最短距離をds_{i},tから頂点iの最短距離をdt_{i}とします。また、stの距離を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)が重複して数えられることも似たような考えからありえません。