Timing [Aizu Competitive Programming Camp 2018 Day 2 F]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/F

考察過程

1. まず面倒なt+ceil(b/(t+a))について考えてみると、tについて下に凸の関数になっている
2. ダイクストラかな？
3. 三分探索すれば、いつまで待てばいいかわかりそう
4. 下に凸だが単調増加・減少をしてないじゃん
5. どうしよう
6. 他の人の提出をみる
7. 少し条件を緩めたt+b/(t+a)でみると、単調増加・減少している
8. 三分探索するときに比較関数をこっちでやるといい感じになる

解説

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day2/3152839

ダイクストラする。
遷移する時に待つかどうかであるが、t+ceil(b/(t+a))は下に凸の関数なので、三分探索する。
f(t) := t + ceil(b/(t+a))とする。
三分探索するときに、そのまま関数fを使うと、同じ値になる区間が存在してしまう可能性があるので厳しい。
よって、関数fを制約がゆるい関数に変えて比較する。
fd(t) := t + b/(t + a)
これなら単調増加・減少になる。
これで、大体の位置が分かるので、求まったtと切り捨てだった場合のt+1のどちらかが本当の答え。
f(t)とf(t+1)を比較して、小さい方を遷移先の到着時間となる。
これでダイクストラができそうだ。

int N, M, S, G, U[201010], V[201010]; ll A[201010], B[201010];
vector<pair<int,int>> E[201010];
ll dst[201010]; int vis[201010];
ll line[201010];
//---------------------------------------------------------------------------------------------------
ll a, b;
ll f(ll x) {
    return x + (b + x + a - 1) / (x + a);
}
double fd(double x) {
    return x + 1.0 * b / (x + 1.0 * a);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> S >> G;
    S--; G--;
    rep(i, 0, M) {
        cin >> U[i] >> V[i] >> A[i] >> B[i];
        U[i]--; V[i]--;

        E[U[i]].push_back({ V[i], i });
        E[V[i]].push_back({ U[i], i });
    }

    rep(i, 0, N) dst[i] = infl;

    min_priority_queue<pair<ll, int>> que;
    que.push({0, S});
    dst[S] = 0;
    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll d = q.first;
        int cu = q.second;

        if (vis[cu]) continue;
        vis[cu] = 1;

        if (cu == G) {
            printf("%lld\n", dst[cu]);
            return;
        }

        fore(p, E[cu]) {
            int to = p.first;
            a = A[p.second];
            b = B[p.second];

            ll t = findMin(d, infl, fd);

            ll nd = min(f(t), f(t + 1));

            if (nd < dst[to]) {
                dst[to] = nd;
                que.push({ nd, to });
            }
        }
    }

    printf("-1\n");
}