はまやんはまやんはまやん

hamayanhamayan's blog

Rush Hour 2 [AtCoder Beginner Contest 204 E]

競技プログラミング

https://atcoder.jp/contests/abc204/tasks/abc204_e

前提知識

解説

https://atcoder.jp/contests/abc204/submissions/23263588

問題設定が有向グラフの最短経路問題なので、ダイクストラ法が最初に思いつく。
ダイクストラ法をもじって解くことをまずは考えていこう。

特殊な条件

一般的なダイクストラと違う点が2点ある。

  • 各都市で整数時間待機できる
  • コストが現在の時間で決定する

まず、上の問題であるが、整数時間待機できるが、各頂点で到達できる時間は一般的なダイクストラ法と同じく最短経路を考えればいい。
時間がかかれば場合によってはコストが小さくなる可能性があるが、それを狙うのであれば、最短経路で進んでから整数時間待機すればいい。
なので、1番目の条件はほとんど問題にならない。
問題は2番目である。

2番目をどう扱うか

以下の問題が解ければ、そのほかはダイクストラ法と全く同じメソッドが使える。
「頂点Aに最短時間cuでいた場合、有向辺で遷移可能な頂点Bに動く場合の最短距離は？」

自明な所から考えていけば、C[i] + floor(D[i] / (t + 1))という式からtがD[i]以上の場合は割り算部分が0になるので、tはD[i]以下だけ考えればいい。
と考えると、遷移の可能性は最短時間cuからD[i]のいずれかとなる。
もっと言うと、最短時間cuがD[i]を超えている場合もあるので、その場合は待つメリットがないので、最短距離cuを採用すればいい。

遷移先を減らすことができたが、この後が問題。
というか三分探索してWAして、絶望してた。

最適な時間は？

C[i] + floor(D[i] / (t + 1))の最短時間はどの辺だろうということを考えると、相加相乗平均を思い出すとsqrt(D[i])あたりだろうなぁという想像がつく。
言われてみれば確かにという感じ…
床関数を外した場合の最小値が、外さなかった場合の最小値とほぼ一緒（全く一緒なのかな？分からない）というのは確かにどこかで見たことがある気がする。
そのあたりで最適な時間を探して答えを見つけよう。

基本的には遷移は無駄に確認しても、最適解は導くことができる。
なので自分の実装では、とりあえず全く待たない場合にかかる時間を求めておいて、そのあとに、sqrt(D[i])の±10くらいの時間で、
かつ、現在の最短時間以降の時間を使って計算するようにしている。
このことに気が付けば、それ以外は特に難しくない。

int N, M;
int A[101010], B[101010], C[101010], D[101010];
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[101010];
ll dist[101010];
//---------------------------------------------------------------------------------------------------
ll calc(ll cur, ll c, ll d) {
    return cur + c + d / (cur + 1);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        A[i]--; B[i]--;
        E[A[i]].push_back(i);
        E[B[i]].push_back(i);
    }

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

    min_priority_queue<pair<ll, int>> que;

    dist[0] = 0;
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

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

        if (cu == N - 1) {
            cout << cst << endl;
            return;
        }

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

        fore(idx, E[cu]) {
            int to = A[idx] + B[idx] - cu;

            ll cst2 = calc(cst, C[idx], D[idx]);

            ll sqr = sqrt(D[idx]);
            rep(d, -10, 10) if (cst <= sqr + d) chmin(cst2, calc(sqr + d, C[idx], D[idx]));
            if (chmin(dist[to], cst2)) que.push({ dist[to], to });
        }
    }

    cout << -1 << endl;
}