ABC051 D - Candidates of No Shortest Paths

問題
提出コード

解法

,を距離で通る辺が使用されるには、との最短距離がになっていればいいです。最短距離になっていない場合、とを通るより最短距離になっているルートを通る方がいかなる場合にも距離が短くなるため、とにおいての最短距離がかどうかだけ調べればよいです。
ということで、辺の状態を保存し、それとは別にワーシャルフロイド法で全ての頂点間の最短距離を求め、最後に保存した辺が最短距離になっているかどうか調べればよいです。
最短距離になっていないものの個数が答えになります。
制約も、頂点の個数が100以下なので、ワーシャルフロイド法が間に合います。