\(O(N^4)\) の解法を紹介します。

\(N\) 頂点のグラフを用意し、頂点 \(i\) から \(j\) への辺のコストを「\(i\) 番目のジャンプ台から \(j\) 番目のジャンプ台へ直接移動するために必要なジャンプ力の最小値」とします。辺のないグラフから始めてコストの小さい辺から順に追加していき、「全ての頂点へ移動可能な頂点」ができたとき、最後に追加した辺のコストが求める答えです。

\(dp[i][s][g]\) を「\(i\) 番目の辺を追加した時点で、\(s\) から \(g\) へ移動可能か」を表す真偽値としたDPを考えます。\(i+1\) 番目の辺 \((v,u)\) を追加する前と後で、\(s\) から \(g\) への移動可能性は次のように変化します

• \(s,g\) がもともと移動可能なら、辺の追加後も移動可能
• \(s,g\) がもともと移動不可能でも、\(s\) から \(v\) へ移動可能で、\(u\) から \(g\) へも移動可能なら、辺の追加後には移動可能になる
• それ以外の場合、辺の追加後も移動不可能

したがって全ての頂点対について実際にこの方法で辺の追加後の移動可能性を確認することで、\(dp[i][*][*]\) から \(dp[i+1][*][*]\) を \(O(N^2)\) で求めることができます。辺の数は \(O(N^2)\) なので、全体で \(O(N^4)\) でDPテーブルを埋めることができ、答えを求めることができます。

C++などの高速な言語であれば比較的余裕を持って(1秒未満で)ACすることができます。
実装例(C++)

余談：

• DPの状態の持ち方を少し替えることで最短経路問題を解くこともできます。
• このアルゴリズムの計算量は辺の数を \(M\) としたとき \(O(N^2M)\) です。
• 疎グラフの辺の使用を何らかの順序で制限したときの、任意の頂点間の最短経路を求める際には、このアルゴリズムによって計算量の改善が見込めます。……と言いたいところですが、大抵の制約では必要なところだけダイクストラをする方が計算量がよくなります。
• このアルゴリズムが「辺を追加しながら最短経路を求めるアルゴリズム」であるのに対し、「頂点を追加しながら最短経路を求めるアルゴリズム」を考えるとワーシャルフロイド法になります。
• ところで、一般にboolを値にもつのDPは効率が悪いです。このアルゴリズムにおいて、移動可能性ではなく最短距離(パス上の辺のコストのmaxのmin)を持つことにすると、辺の追加順序を気にする必要がなくなるためワーシャルフロイド法により \(O(N^3)\) で解くことができます。