算法

(Dijkstra) $O(n + m\log m)$

如果不加 $k$ 的限制的话，容易发现这题就是个 $\rm Dijkstra$ 裸题，而加了 $k$ 这个限制的话，对于火车 $i$ 而言，城市 $A_i$ 到城市 $B_i$ 的时间为 $T_i$，如果在 $T$ 时刻你在城市 $A$，那么你可以到达 $B_i$ 的最早时间应该是 $\left\lceil {\frac{T}{K_i}} \right\rceil * K_i + T_i$。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); ++i)

using namespace std;
using ll = long long;
using P = pair<ll, int>;

struct Edge {
    int to, t, k;
    Edge(int to, int t, int k): to(to), t(t), k(k) {}
};

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--; y--;

    vector<vector<Edge>> g(n);
    rep(i, m) {
        int a, b, t, k;
        cin >> a >> b >> t >> k;
        --a; --b;
        g[a].emplace_back(b, t, k);
        g[b].emplace_back(a, t, k);
    }

    const ll INF = 1e18;
    vector<ll> dist(n, INF);
    priority_queue<P, vector<P>, greater<P>> q;
    auto push = [&](int v, ll x) {
        if (dist[v] <= x) return;
        dist[v] = x;
        q.emplace(x, v);
    };
    push(x, 0);
    while (q.size()) {
        auto [x, v] = q.top(); q.pop();
        if (dist[v] != x) continue;
        for (Edge& e : g[v]) {
            ll nx = (x + e.k - 1) / e.k * e.k + e.t;
            push(e.to, nx);
        }
    }

    ll ans = dist[y];
    if (ans == INF) ans = -1;
    cout << ans << '\n';

    return 0;
}