A1133 [CSP-J 2023] 旅游巴士

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

    // g[u]：从 u 出发的道路 (终点, 开放时间)
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, a;
        cin >> u >> v >> a;
        g[u].push_back({v, a});
    }

    const long long INF = (1LL << 60);

    // dis[v][r]：到达地点 v、且当前时刻模 k 等于 r 的最早时刻
    vector<vector<long long>> dis(n + 1, vector<long long>(k, INF));

    using State = tuple<long long, int, int>;   // 时刻, 地点, 余数
    priority_queue<State, vector<State>, greater<State>> pq;

    dis[1][0] = 0;   // 时刻 0 乘巴士进入景区
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        auto [t, u, r] = pq.top();
        pq.pop();
        if (t != dis[u][r]) continue;

        for (auto [v, a] : g[u]) {
            long long T = t;
            if (T + 1 < a) {
                // 这条路还没开放：坐更晚一班的巴士进景区，把时刻推迟 k 的整数倍
                long long need = a - 1 - T;
                T += ((need + k - 1) / k) * k;
            }
            int nr = (r + 1) % k;
            long long nt = T + 1;
            if (nt < dis[v][nr]) {
                dis[v][nr] = nt;
                pq.push({nt, v, nr});
            }
        }
    }

    // 离开景区的时刻必须是 k 的倍数
    if (dis[n][0] == INF) cout << -1 << '\n';
    else cout << dis[n][0] << '\n';
    return 0;
}