ABC051 : D - Candidates of No Shortest Paths

問題

無向連結グラフが与えられ、全頂点間の最短パスに使われていない辺の数を求める問題。

解法

頂点の数が <= 100 なので、ワーシャルフロイド法で全頂点間の最短距離を求める。その後、各辺について、全頂点から両端の頂点までの距離の差がその辺のコストになっているかを調べ、なっていないものがあればその辺を答えに加算する。ワーシャルフロイド法で使う配列の初期化を忘れてしまうミスを犯した...