ここで、\(t\) を定めるごとに \(f(t)\) を与える \(P\) を得ることができます。 これを \(P _ t\) と書くことにします。

Dinkelbach algorithm は、\(t\) を適切な初期値にとり、\(t\leftarrow\dfrac{B(P _ t)}{C(P _ t)}\) で更新することを繰り返すことによって \(f(t)=0\) となる \(t\) を求める手法です（これは、\(f(t)\) の零点を近似するために Newton 法を用いていると見ることもできます）。

この問題の設定（を含む条件）のもとで、Dinkelbach algorithm は有限回の繰り返しで \(f(t)=0\) なる \(t\) に収束することが示されています。 この問題で用いられたテストケースでは、たかだか \(5\) 回の繰り返しで収束することが確かめられます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <limits>
#include <iomanip>

int main() {
    using namespace std;
    
    unsigned N, M;
    cin >> N >> M;
    vector<vector<tuple<unsigned, unsigned, unsigned>>> edges(N);
    for (unsigned u, v, b, c; [[maybe_unused]] const auto _ : views::iota(0U, M)) {
        cin >> u >> v >> b >> c;
        edges[--u].emplace_back(--v, b, c);
    }

    // dp[i] := 頂点 i に到達するための (合計美しさ, 合計コスト) の中で 合計美しさ * y - 合計コスト * x が最大のもの
    vector<pair<unsigned long, unsigned long>> dp(N, {0, numeric_limits<unsigned>::max()});
    dp[0] = {0, 0};

    // 配る DP で B(P_t) / C(P_t) を求める
    const auto iteration{[N, &edges, &dp](unsigned long x, unsigned long y) -> pair<unsigned long, unsigned long>& {
        for (const auto u : views::iota(0UL, N))
            for (const auto&[u_b, u_c]{dp[u]}; const auto&[v, b, c] : edges[u])
                if (dp[v].first * y + (u_c + c) * x < (u_b + b) * y + dp[v].second * x) // より大きければ更新
                    dp[v] = {u_b + b, u_c + c};
        return dp.back();
    }};

    pair<unsigned long, unsigned long> t{1, 0}, prev{};
    auto&&[x, y]{t};
    do
        swap(t, prev = iteration(x, y));
    while (t != prev); // 収束したらループを抜ける
    
    cout << fixed << setprecision(10) << static_cast<long double>(x) / y << endl;
    
    return 0;
}