Train [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) E]

https://atcoder.jp/contests/abc192/tasks/abc192_e

前提知識

• ダイクストラ

解説

https://atcoder.jp/contests/abc192/submissions/20346183

ダイクストラ法で解く。
ダイクストラから少ししか変更がないので、ダイクストラを一通り勉強した後の1up問題として最適。

問題はどうやってダイクストラに乗せるかであるが、一般的なダイクストラ同様に
D[cu] := 都市cuに到着する最短時間
を作って更新していけばいい。
問題は遷移時であるが、遷移時はKの倍数でしか出発できないので、遷移前の時間から最も近いKの倍数の時間を計算して、
そこからTで時間を延ばして遷移させる。
この遷移部分のみが、一般的なダイクストラ法と異なる。
他は一緒。
ちなみに、自分の実装では、一番近いKの倍数を得るのに、Kで切り上げをしてからKをかけるという方法を取っている。

int N, M, X, Y;
int A[101010], B[101010], T[101010], K[101010];
vector<pair<int, pair<int,int>>> E[101010];
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[101010];
ll D[101010];
ll dijk() {
    rep(i, 0, N) D[i] = infl;
    rep(i, 0, N) vis[i] = 0;

    min_priority_queue<pair<ll, int>> que;

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

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

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

        if (cu == Y) return D[Y];

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

        fore(p, E[cu]) {
            int to = p.first;
            int T = p.second.first;
            int K = p.second.second;

            ll cst2 = (cst + K - 1) / K * K + T;
            if (chmin(D[to], cst2)) que.push({ D[to], to });
        }
    }

    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> X >> Y;
    X--; Y--;
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> T[i] >> K[i];
        A[i]--; B[i]--;

        E[A[i]].push_back({ B[i], {T[i], K[i]} });
        E[B[i]].push_back({ A[i], {T[i], K[i]} });
    }

    ll ans = dijk();
    cout << ans << endl;
}