AtCoder Regular Contest 090 E - Avoiding Collision

https://beta.atcoder.jp/contests/arc090/tasks/arc090_c

問題

無向グラフ G が与えられる。 2頂点 S、T が与えられる。 A さんは頂点 S から頂点 T に向かう 。Bさんは頂点 T から頂点 S に向かう。A さんも B さんも最短路をとる。 このとき Aさんと Bさんが出会わないような経路の 組み合わせの数を求めよ。

アプローチ

　前処理として頂点 S から各頂点への 最短距離とその最短距離を満たすような経路の取り方の数を求めておく。これはダイクストラ 法によって計算できる。

　A さんと Bさんが出会う経路の組み合わせも含めると、その組み合わせの数はSから T に最短路で向かうような組み合わせの数の２乗で表される。ここからAさんとBさんが出会うような組み合わせの数を引き算することでAさんとBさんが出会わないような経路の組み合わせ数を求める。

　A さんとBさんのそれぞれが目的の頂点に向かうときAさんとBさんが出会うのはたかだか一回だけである。AさんとBさんが出会うのは辺上で出会う場合と頂点上で出会う二つのパターンがある。AさんとBさんが頂点vで出会うのはdist(S,v)==dist(T,v)のときである。またある辺e=(u,v)で AさんとBさんが出会うのはdist(A,u)＜dist(S,T)/2＜dist(A,u)+e.lengthの式が成立する時である。この二つの場合の数を引けばよい。