No.051 D

まずは任意の2点間の最短距離を Floyd Warshal 法で求めておく. 頂点 $i, j$ 間の最短距離を $D(i, j)$ とする.

頂点 $i$ からの最短距離に辺 $j$ が含まれるかどうかであるが, これは $i \rightarrow a_j \rightarrow b_j$ が最短ルートになるか, $i \rightarrow b_j \rightarrow a_j$ が最短ルートになるかのどちらかが成り立つときである.

すなわち,

$$D(i, a_j) + c_j = D(i, b_j) \\ D(i, b_j) + c_j = D(i, a_j)$$

のどちらかが成り立てば, 辺 $j$ は最短ルートに含まれる.

これをすべての $i, j$ について検証して, 最短ルートに含まれない辺の数を求める.