第2回 ドワンゴからの挑戦状 予選: C - メンテナンス明け

https://beta.atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_c

問題概要

N個の駅とM個の路線が与えられる。各路線はLi個の駅を順につないだ単純パスになっており、各辺に移動時間が設定されている。駅srcから駅dstに向かいたいが、一度だけ寝過ごす可能性があり、寝過ごした場合は路線の終点まで強制的に移動する。一度寝過ごしたあとは二度と寝過ごすことはない。寝過ごしが任意の移動時に起こりうるとき、最大の移動時間を最小化するように移動したい。そのような場合の移動時間を求めよ。

N <= 25252

各路線に含まれる駅数の和 <= 252525

解法

二分探索をする。

  • 必要な考察1. 仮に寝過ごしが発生した場合、寝過ごし後にたどり着く終点からdstまでは最小移動時間で行ける。またその最小移動時間はdstを始点にして1回ダイクストラを回せばすべての頂点に対して計算可能である。
  • 必要な考察2. まだ寝過ごしが発生していない状態である辺を使って移動するとき、「仮にその移動で寝過ごしが発生した場合のdstまでの移動時間」は考察1より確定できる。

ここで「使っていい時間の最大値」を定めると、「もしある辺を使った移動で寝過ごしが起きたとき、移動時間が設定した最大値を超えるならばその辺を使うことはできない」ということが言える。よって二分探索の各ループではsrcから普通にダイクストラを回しつつ上の方法で禁止されない辺だけを使って移動していき、最終的にdstにたどり着けるかを見ればよい。

感想

あーすごい、こうやるのかというかんじ

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    immutable long INF = 1L << 59;
    
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = s[2];
    auto T = s[3];
    auto L = new int[](M);
    auto A = new int[][](M);
    auto W = new long[][](M);
    auto G = new Tuple!(int, long, int, long)[][](N);
    foreach (i; 0..M) {
        L[i] = readln.chomp.to!int;
        A[i] = readln.split.map!(to!int).array;
        W[i] = readln.split.map!(to!long).array;
        long acm1 = W[i].sum;
        long acm2 = 0;
        foreach (j; 0..L[i]-1) {
            acm2 += W[i][j];
            G[A[i][j]] ~= tuple(A[i][j+1], W[i][j], A[i].back, acm1);
            G[A[i][j+1]] ~= tuple(A[i][j], W[i][j], A[i].front, acm2);
            acm1 -= W[i][j];
        }
    }

    auto shortest = new long[](N);
    shortest.fill(INF);
    auto pq = new BinaryHeap!(Array!(Tuple!(int, long)), "a[1] > b[1]")();
    auto dist = new long[](N);

    pq.insert(tuple(T, 0L));
    while (!pq.empty) {
        auto t = pq.front;
        auto n = t[0];
        auto d = t[1];
        pq.removeFront;
        if (shortest[n] <= d) continue;
        shortest[n] = d;
        foreach (to; G[n]) {
            auto nn = to[0];
            auto nd = d + to[1];
            if (shortest[nn] <= nd) continue;
            pq.insert(tuple(nn, nd));
        }
    }


    long hi = 10L^^15;
    long lo = 0;
    
    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        dist.fill(INF);
        pq.clear();
        pq.insert(tuple(S, 0L));
        bool ok = false;

        while (!pq.empty) {
            auto t = pq.front;
            auto n = t[0];
            auto d = t[1];
            pq.removeFront;
            if (n == T) {
                ok = true;
                break;
            }
            if (dist[n] <= d) continue;
            dist[n] = d;
            foreach (to; G[n]) {
                auto nn = to[0];
                auto nd = d + to[1];
                auto zzz = to[2];
                auto zzz_d = d + to[3];
                if (zzz_d + shortest[zzz] > mid) continue;
                if (dist[nn] <= nd) continue;
                if (nd > mid) continue;
                pq.insert(tuple(nn, nd));
            }
        }

        if (ok) hi = mid;
        else lo = mid;

    }
    
    hi.writeln;
}