[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)\]
は常に成り立ちます。

コード

提出したコード

ワーシャルフロイド法

void warshall_floyd() {
  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      if (d[i][k] == INF) continue;
      for (int j = 0; j < N; j++) {
        if (d[k][j] == INF) continue;
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}