[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]); } } } }
ディスカッション
コメント一覧
まだ、コメントがありません