test/Other/golden_search/aoj-3044.cpp

• View this file on GitHub
• Last update: 2025-12-15 21:04:19+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3044

Depends on

• Other/golden_search.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3044

#include "Other/golden_search.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long N, M, S, G;
    cin >> N >> M >> S >> G;
    S--, G--;

    vector<vector<tuple<int, long long, long long>>> edges(N);
    for (int i = 0; i < M; i++)
    {
        long long U, V, A, B;
        cin >> U >> V >> A >> B;
        U--, V--;

        edges[U].push_back({V, A, B});
        edges[V].push_back({U, A, B});
    }

    vector<long long> dists(N, LONG_LONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dists[S] = 0;
    pq.push({0, S});

    while (pq.size())
    {
        auto [dist, now] = pq.top();
        pq.pop();

        if (dists[now] < dist)
        {
            continue;
        }

        for (auto [next, A, B] : edges[now])
        {
            auto f = [&](double t) -> double
            {
                return t + (double)B / (t + (double)A);
            };

            auto start = golden_search<true, double>(dist, 1e20, f).first;

            auto f_int = [&](long long t) -> long long
            {
                return t + (B + t + A - 1) / (t + A);
            };

            long long next_dist = min(f_int(floor(start)), f_int(ceil(start)));
            if (dists[next] <= next_dist)
            {
                continue;
            }

            dists[next] = next_dist;
            pq.push({next_dist, next});
        }
    }

    long long ans = dists[G];
    if (ans == LONG_LONG_MAX)
    {
        ans = -1;
    }
    cout << ans << endl;

    return 0;
};

#line 1 "test/Other/golden_search/aoj-3044.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3044

#line 1 "Other/golden_search.hpp"
#include <bits/stdc++.h>
using namespace std;

// フィボナッチ数列による三分探索。「狭義」凸関数の極値を探索する。返り値は{x, f(x)}
template <bool Minimize, typename T>
pair<double, T> golden_search(double x_low, double x_high, function<T(double)> f)
{
    assert(x_low <= x_high);

    auto comp = [](T a, T b) -> bool
    {
        return Minimize ? a <= b : a >= b;
    };

    const double PHI = 1.61803398874989484;     // (1 + √5) / 2
    const double DIVPHI = 0.381966011250105151; // 1 / (1 + PHI);

    double x_mid_low = (x_low * PHI + x_high) * DIVPHI;
    double x_mid_high = (x_low + x_high * PHI) * DIVPHI;

    double f_low = f(x_low), f_mid_low = f(x_mid_low), f_mid_high = f(x_mid_high), f_high = f(x_high);

    for (int iter = 0; iter < 100; iter++)
    {
        if (comp(f_mid_low, f_mid_high))
        {
            tie(x_mid_low, x_mid_high, x_high) = tuple<double, double, double>{(x_low * PHI + x_mid_high) * DIVPHI, x_mid_low, x_mid_high};
            tie(f_mid_low, f_mid_high, f_high) = tuple<double, double, double>{f(x_mid_low), f_mid_low, f_mid_high};
        }
        else
        {
            tie(x_low, x_mid_low, x_mid_high) = tuple<double, double, double>{x_mid_low, x_mid_high, (x_mid_low + x_high * PHI) * DIVPHI};
            tie(f_low, f_mid_low, f_mid_high) = tuple<double, double, double>{f_mid_low, f_mid_high, f(x_mid_high)};
        }
    }

    return {x_low, f_low};
}
#line 5 "test/Other/golden_search/aoj-3044.cpp"

using namespace std;

int main()
{
    long long N, M, S, G;
    cin >> N >> M >> S >> G;
    S--, G--;

    vector<vector<tuple<int, long long, long long>>> edges(N);
    for (int i = 0; i < M; i++)
    {
        long long U, V, A, B;
        cin >> U >> V >> A >> B;
        U--, V--;

        edges[U].push_back({V, A, B});
        edges[V].push_back({U, A, B});
    }

    vector<long long> dists(N, LONG_LONG_MAX);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dists[S] = 0;
    pq.push({0, S});

    while (pq.size())
    {
        auto [dist, now] = pq.top();
        pq.pop();

        if (dists[now] < dist)
        {
            continue;
        }

        for (auto [next, A, B] : edges[now])
        {
            auto f = [&](double t) -> double
            {
                return t + (double)B / (t + (double)A);
            };

            auto start = golden_search<true, double>(dist, 1e20, f).first;

            auto f_int = [&](long long t) -> long long
            {
                return t + (B + t + A - 1) / (t + A);
            };

            long long next_dist = min(f_int(floor(start)), f_int(ceil(start)));
            if (dists[next] <= next_dist)
            {
                continue;
            }

            dists[next] = next_dist;
            pq.push({next_dist, next});
        }
    }

    long long ans = dists[G];
    if (ans == LONG_LONG_MAX)
    {
        ans = -1;
    }
    cout << ans << endl;

    return 0;
};

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	3 MB
g++	00_sample_01.in	AC	4 ms	3 MB
g++	00_sample_02.in	AC	4 ms	3 MB
g++	00_sample_03.in	AC	4 ms	3 MB
g++	00_sample_04.in	AC	4 ms	3 MB
g++	02_random_01.in	AC	5 ms	4 MB
g++	02_random_02.in	AC	5 ms	3 MB
g++	02_random_03.in	AC	5 ms	3 MB
g++	02_random_04.in	AC	5 ms	4 MB
g++	02_random_05.in	AC	5 ms	4 MB
g++	02_random_06.in	AC	5 ms	3 MB
g++	02_random_07.in	AC	5 ms	4 MB
g++	02_random_08.in	AC	6 ms	4 MB
g++	02_random_09.in	AC	5 ms	4 MB
g++	02_random_10.in	AC	5 ms	4 MB
g++	03_large_01.in	AC	200 ms	17 MB
g++	03_large_02.in	AC	188 ms	15 MB
g++	03_large_03.in	AC	421 ms	20 MB
g++	03_large_04.in	AC	338 ms	18 MB
g++	03_large_05.in	AC	369 ms	19 MB
g++	12_random_drastic_01.in	AC	6 ms	4 MB
g++	12_random_drastic_02.in	AC	5 ms	4 MB
g++	12_random_drastic_03.in	AC	5 ms	4 MB
g++	12_random_drastic_04.in	AC	5 ms	4 MB
g++	12_random_drastic_05.in	AC	5 ms	4 MB
g++	12_random_drastic_06.in	AC	5 ms	3 MB
g++	12_random_drastic_07.in	AC	5 ms	4 MB
g++	12_random_drastic_08.in	AC	6 ms	3 MB
g++	12_random_drastic_09.in	AC	6 ms	4 MB
g++	12_random_drastic_10.in	AC	5 ms	3 MB
g++	13_large_drastic_01.in	AC	290 ms	18 MB
g++	13_large_drastic_02.in	AC	145 ms	16 MB
g++	13_large_drastic_03.in	AC	345 ms	20 MB
g++	13_large_drastic_04.in	AC	287 ms	18 MB
g++	13_large_drastic_05.in	AC	260 ms	18 MB
g++	24_mukade_large_01.in	AC	455 ms	26 MB
g++	24_mukade_large_02.in	AC	463 ms	26 MB
g++	24_mukade_large_03.in	AC	478 ms	26 MB
g++	24_mukade_large_04.in	AC	469 ms	27 MB
g++	24_mukade_large_05.in	AC	426 ms	25 MB
g++	25_shell_large_01.in	AC	319 ms	19 MB
g++	25_shell_large_02.in	AC	242 ms	14 MB
g++	25_shell_large_03.in	AC	247 ms	14 MB
g++	25_shell_large_04.in	AC	357 ms	20 MB
g++	25_shell_large_05.in	AC	269 ms	17 MB
g++	90_corner_01.in	AC	5 ms	3 MB
g++	90_corner_02.in	AC	4 ms	3 MB
g++	90_corner_03.in	AC	4 ms	3 MB
g++	90_corner_04.in	AC	4 ms	3 MB
g++	90_corner_05.in	AC	4 ms	3 MB
g++	90_corner_06.in	AC	4 ms	3 MB
g++	90_corner_07.in	AC	4 ms	3 MB
g++	90_corner_08.in	AC	4 ms	3 MB
g++	90_corner_09.in	AC	4 ms	3 MB
g++	90_corner_10.in	AC	4 ms	3 MB
g++	91_corner2_01.in	AC	289 ms	18 MB
g++	91_corner2_02.in	AC	224 ms	11 MB
g++	91_corner2_03.in	AC	213 ms	11 MB
g++	91_corner2_04.in	AC	321 ms	19 MB
g++	91_corner2_05.in	AC	350 ms	18 MB
g++	99_hand_01.in	AC	5 ms	3 MB
g++	99_hand_02.in	AC	4 ms	3 MB
g++	99_hand_03.in	AC	4 ms	3 MB

Back to top page