[AtCoder] ABC051 D – Candidates of No Shortest Paths

Candidates of No Shortest Paths

CSAcademyのLong Journeyと似たような考え方が必要だと思いました。

考え方

題意

全点間の最短経路において、全ての最短経路の中で一度も通ることがない辺の本数を求めます。

方針

全点間の最短経路を求めます。これはワーシャルフロイドなどで求めることができます。ワーシャルフロイドについては、下の記事で扱ったことがありました。

https://yamakasa3.hatenablog.com/entry/2018/10/06/184536

点 \( (i, j) \) 間の最短距離を \( d(i, j) \) とします。辺 \( a, b\) がこの最短経路に含まれる場合、辺 \( a, b\) の重みを \( c(a, b)\) として、

\[ d(i, j) = d(i, a) + c(a, b) + d(b, j)\]

を満たします。\( d(a, b)\) としない理由は、\( c(a, b) > d(a, b)\) となる可能性があるためです。

また、

\[ d(i, j) = d(i, a) + d(a, b) + d(b, j)\]

は常に成り立ちます。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする