[AtCoder] ABC 192 E – Train
問題
方針
都市 \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません