実数 \(X\) に対して、

本問題の答えが \(X\) 以上か？

という判定問題が十分高速に解ければ、本問題の答えはこの判定問題の答えが真である最小の実数として、二分探索で（正解するために十分な精度まで）十分高速に求められます。 よって、以下では実数 \(X\) を固定して、この判定問題を解くことを考えます。

本問題の答えが \(X\) 以上であることは、 頂点 \(1\) から頂点 \(N\) へのパスであって、美しさの総和をコストの総和で割った値が \(X\) 以上のものが存在すること、 すなわち、頂点 \(1\) から頂点 \(N\) へのパス（辺の番号の列） \((i_1, i_2, \ldots, i_l)\) であって、

\[ \frac{\sum_{k = 1}^l b_{i_k}} {\sum_{k = 1}^l c_{i_k}} \geq X \]

を満たすものが存在することと同値です。 この条件式は

\[ \sum_{k = 1}^l (b_{i_k} - c_{i_k}X) \geq 0 \]

と書き換えられるので、 各辺についてその重みを \(w_i \coloneqq b_i - c_iX\) で定めると、「本問題の答えが \(X\) 以上」であることは、頂点 \(1\) から頂点 \(N\) へのパスであってそのパスの重み（パス上の辺の重みの総和）

\[ \sum_{k=1}^l w_{i_k} = \sum_{k = 1}^l (b_{i_k} - c_{i_k}X) \]

が \(0\) 以上のものが存在することと同値です。 よって、所望の判定問題を解くには、頂点 \(1\) から頂点 \(N\) へのパスの重みとしてあり得る最大値を求め、その値が \(0\) 以上かを判定すれば良いです。

「頂点 \(1\) から頂点 \(N\) へのパスの重みとしてあり得る最大値」を求める問題は、最短経路問題と同様にして解くことができます。 特に、本問題で与えられるグラフは頂点番号が小さい方から大きい方にのみ辺が張られた DAG であるため、 頂点番号の小さい方から、

\(\mathrm{dp}[i] := \)（頂点 \(1\) から頂点 \(i\) までのパスの重みとしてあり得る最大値）

というテーブルを頂点番号 \(i\) の小さい方から順に埋めていく、動的計画法によって \(O(M)\) 時間で求めることができます。