思路与算法

以地点u和当前时刻模k为状态，维护能从某个合法入园时刻到达该状态的最早绝对时间t。沿开放时间a的边时，若t<a，就把整条已走路径的起始时间向后平移ceil((a-t)/k)*k，接着走一单位时间。Dijkstra取最早时间，目标是出口且余数0。

正确性说明

相同状态的较晚合法到达时刻，与最早到达时刻相差k的整数倍。可以把最早方案的入园与沿途每一步整体后移这些时间，开放下界不会被破坏，因此早到方案支配所有晚到方案；这是一开始晚出发，不是在景区停留。过边取不早于开放时刻且余数相同的最小时刻，转移关于t单调且至少增加1，Dijkstra按非减时间确定状态正确。目标余数0恰满足乘车离开要求。

复杂度

O((nk+mk)log(nk))时间、O(nk+m)空间，含nk距离数组与图初始化。

易错点

不能简单在每个点原地等待，也不能只用每个地点一个距离。允许走环调整余数；无符合出口余数的路径输出-1。所有开门时间只限制出发走该边的时刻。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        g[a - 1].push_back({b - 1, t});
    }
    const long long INF = 1LL << 60;
    vector<long long> d(n * k, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        q;
    d[0] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        long long tm = cur.first;
        int state = cur.second, u = state / k, mod = state % k;
        if (tm != d[state])
            continue;
        if (u == n - 1 && !mod) {
            cout << tm << "\n";
            return 0;
        }
        for (auto e : g[u]) {
            long long t = tm;
            if (t < e.second)
                t += (e.second - t + k - 1) / k * k;
            t++;
            int v = e.first * k + (mod + 1) % k;
            if (t < d[v]) {
                d[v] = t;
                q.push({t, v});
            }
        }
    }
    cout << -1 << "\n";
}