[AtCoder] ABC061 D – Score Attack

Score Attack

https://atcoder.jp/contests/abc061/tasks/abc061_d

グラフの問題です。

考え方

題意

頂点 \( 1 \) から頂点 \( N \) からまでのパスにおいて、最大距離を求める問題です。パスの存在は保証されますが、閉路が存在するので、距離が無限大となるときは inf を出力します。

方針

グラフの問題では最短距離を答える問題が多いと思いますが、今回は違います。このような問題では、重みの符号を反転させ、最短経路問題に帰着させます。

これは、\( y = f(x) \) の最大化問題を \( y = -f(x) \) の最小化問題として解くようなものだと思います。

与えられるグラフでは負閉路が存在する可能性があるので、負閉路の検出をする必要があります。到達可能な負閉路が存在したとしても、頂点 \( 1 \) から頂点 \( N \) のパスに負閉路が存在しなければ、スコアが発散することはありません。

負閉路の検出はベルマン–フォードのアルゴリズムが適切だと思います。このアルゴリズムを適用する上で注意する点は下のサイトで述べられています。

http://sesenosannko.hatenablog.com/entry/2017/09/01/214852

この問題では上記のサイトの type C を使うことになります。

コード

シェアする

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

フォローする