G - Jumping Takahashi 2 解説
by 
kyopro_friends
\(O(N^3)\) の解法を紹介します。
\(N\) 頂点のグラフを用意し、頂点 \(i\) から \(j\) への辺のコストを「\(i\) 番目のジャンプ台から \(j\) 番目のジャンプ台へ直接移動するために必要なジャンプ力の最小値」とします。
ジャンプ力 \(P\) の状態で、あるパスによってジャンプ台 \(i\) から \(j\) へ間接的に移動できるためには、そのパスに含まれる辺のコストが全て \(P\) 以下であることが必要十分です。したがって、\(i\) から \(j\) へ間接的に移動可能な最小のジャンプ力は、辺のコストのmaxを取る最短距離となります。
どういうこと？
パス $p$ で $x$ から $y$ まで移動するときの距離を $f(p)$、パス $q$ で $y$ から $z$ まで移動するときの距離を $f(q)$ とし、この2つのパスを繋げたパス $r$ によって $x$ から $z$ まで移動するときの距離を $f(r)$ とします。普通の距離であれば、$f(r)=f(p)+f(q)$ です。今回は、パスに含まれる辺のコストのmaxにだけ興味があるので、$f(r)=\max(f(p),f(q))$ です。実は、この変な距離でもワーシャルフロイド法は正しく動作するため、\(O(N^3)\) で全頂点対の最短距離を求めることができ、元の問題に答えることができます。
投稿日時:
最終更新: