[AtCoder] ABC 051 D – Candidates of No Shortest Paths

問題

方針

全点間の最短距離を求めます。これはワーシャルフロイドなどで求めることができます。
点 \( (i, j) \) 間の最短距離を \( d(i, j) \) とします。辺 \( a, b\) がこの最短経路に含まれる場合、辺 \( a, b\) の重みを \( c(a, b)\) として、
\[ d(i, j) = d(i, a) + c(a, b) + d(b, j)\]
を満たす \( (i, j)\) が一つでも存在します。\( d(a, b)\) としない理由は、\( c(a, b) < d(a, b)\) となる可能性があるためです。また、
\[ d(i, j) = d(i, a) + d(a, b) + d(b, j)\]
は常に成り立ちます。

コード

提出したコード

ワーシャルフロイド法