AtCoder Beginner Contest 051：D - Candidates of No Shortest Paths
問題
解法
N <= 100 と小さいので，ワーシャルフロイド法を用いて全頂点間の最短コストを更新していく．もし，dist[i][j] > dist[i][k] + dist[k][j] であるならば，辺 (i -> j) はどの最短経路にも含まれない．これを数えていき，与えられた辺のうち数えられたものの個数を答えにすればよい．O(N^2)．
解答
N <= 100 と小さいので，ワーシャルフロイド法を用いて全頂点間の最短コストを更新していく．もし，dist[i][j] > dist[i][k] + dist[k][j] であるならば，辺 (i -> j) はどの最短経路にも含まれない．これを数えていき，与えられた辺のうち数えられたものの個数を答えにすればよい．O(N^2)．