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; }
