[AtCoder] ABC 192 E – Train

2021年3月1日

問題

方針

都市 \( X \) から都市 \( i \) へたどり着いたときの最短時間を \( d_i \) とします。初期値は、\( d_X = 0, d_i = \infty \ (i \neq X) \) とします。 また、鉄道が都市 \( i \) と都市 \( j \) を結ぶ時、時刻が \( K(i, j) \) の倍数になる毎に列車が発車して、\( T(i, j) \) 時間かかるとします。

都市 \( i \) から都市 \( j \) に行くことができる場合、

\[ d_j \leftarrow \min(d_j, K(i, j) \left \lfloor \dfrac{d_i + K(i, j) – 1}{K(i, j)} \right \rfloor + T(i, j))\]

と更新できます。これは、現在の時刻を \( t \) として、\( K \) の倍数の時刻になるまでの最小の経過時間を \( x \) を考えます。これは、

\[ (t + x) \bmod K\]

を満たす \( x \) を求めます。非負整数 \( n \) を用いて、

\[ t + x = nK\]

と表現できるので、\( x = nK – t \geq 0 \) より、

\[ n \geq \dfrac{t}{K}\]

となります。したがって、

\[ t + x = K \left \lfloor \dfrac{t + K – 1}{K} \right \rfloor\]

と求まります。探索の部分はダイクストラ法を用います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    int v;
    ll T, K;
    ll t = LLONG_MAX;
    Node(int v, ll T, ll K) : v(v), T(T), K(K) {}
};

struct Data {
    int v;
    ll t = LLONG_MAX;
    Data(int v, ll t) : v(v), t(t) {}
    bool operator < (const Data &d) const {
        return d.t < t;
    }
};

int main() {
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    X--;
    Y--;
    int A[M], B[M];
    ll T[M], K[M];
    vector<Node> adj[N];
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> T[i] >> K[i];
        A[i]--;
        B[i]--;
        adj[A[i]].push_back(Node(B[i], T[i], K[i]));
        adj[B[i]].push_back(Node(A[i], T[i], K[i]));
    }
    ll d[N];
    fill(d, d + N, LLONG_MAX);
    d[X] = 0;
    priority_queue<Data> pq;
    pq.push(Data(X, 0));
    bool vis[N] = {};
    while (!pq.empty()) {
        int v = pq.top().v;
        pq.pop();
        if (vis[v]) continue;
        vis[v] = true;
        for (Node i : adj[v]) {
            ll t = i.K * ((d[v] + i.K - 1) / i.K) + i.T;
            if (t < d[i.v]) {
                d[i.v] = t;
                pq.push(Data(i.v, t));
            }
        }
    }
    if (d[Y] == LLONG_MAX) {
        cout << "-1\n";
    } else {
        cout << d[Y] << "\n";
    }
    return 0;
}