你好！我是你的OI教练。

这道题（CSP-J 2023 T4 旅游巴士）是当年入门组的压轴题，难度达到了 普及+/提高 的水平。它主要考察 分层图最短路（或者叫拆点最短路）的思想。

解这道题的关键在于如何处理“整除 $k$”这个限制。

1. 题目核心难点分析

• 限制一：必须在 $k$ 的整数倍时刻到达入口，也在 $k$ 的整数倍时刻离开出口。
• 限制二：中间不能停留，每条边耗时 1 单位。这意味着一旦出发，到达某个点的时间模 $k$ 的余数是固定的（只取决于经过了多少条边）。
• 限制三：每条道路有开放时间 $a_i$。如果当前到达 $u$ 的时间 $t < a_i$，我们不能通过。
  • 题目说“不能在路上停留”，但我们可以推迟出发时间。
  • 推迟出发时间必须是 $k$ 的倍数。这意味着，我们可以把当前到达时间 $t$ 增加 $m \times k$，使得 $t + m \times k \ge a_i$。

2. 核心思路：分层图最短路 (Dijkstra)

由于 $k$ 非常小（$k \le 100$），我们可以把每个地点 $u$ 拆成 $k$ 个状态。

• 状态定义：$dist[u][j]$ 表示到达地点 $u$，且当前时间 $t \pmod k = j$ 时的最早可能时间。
• 目标：求 $dist[n][0]$。

3. 状态转移

假设我们现在在点 $u$，当前时间是 $t$（此时 $t \pmod k = j$），有一条边 $u \to v$，限制为 $a$。 到达 $v$ 的时间 $t_{next}$ 计算如下：

1. 如果不受限制：我们直接走过去，耗时 1。
   • 理想时间 $t' = t$。
2. 受限制 $a$：我们需要满足 $actual\_time \ge a$。
   • 如果 $t \ge a$，直接通过，通过时刻为 $t$。
   • 如果 $t < a$，我们需要在起点“晚出发”若干个 $k$。这等价于将当前时间 $t$ 补齐到不小于 $a$ 的最小同余时间。
   • 计算公式：$wait = \lceil \frac{a - t}{k} \rceil \times k$。
   • 实际通过时刻 $pass = t + (\text{如果 } t < a \text{ 则 } wait \text{ 否则 } 0)$。
3. 到达 $v$：
   • 到达时刻 $t_{next} = pass + 1$。
   • 新的余数 $j_{next} = t_{next} \pmod k$。
   • 用 $t_{next}$ 更新 $dist[v][j_{next}]$。

因为边权（时间流逝）非负，且我们贪心地取最早时间，所以可以使用 Dijkstra 算法。

预备知识点总结

要解决这道题，你需要掌握：

1. 图的存储：邻接表（vector）。
2. Dijkstra 算法：优先队列优化版本，用于求最短路。
3. 同余运算：理解模运算的性质。
4. 分层图思想：将一个节点根据状态（这里是时间余数）拆分为多个节点。

标准答案代码 (C++ 14)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
const int MAXK = 105;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, a;
};

struct Node {
    int u, time;
    // 优先队列默认是大根堆，我们需要最小时间优先，所以重载 < 符号
    bool operator>(const Node& other) const {
        return time > other.time;
    }
};

int n, m, k;
vector<Edge> adj[MAXN];
// dist[u][r] 表示到达点 u，且时间 % k == r 的最小时间
int dist[MAXN][MAXK];
bool vis[MAXN][MAXK];

int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n >> m >> k)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v, a;
        cin >> u >> v >> a;
        adj[u].push_back({v, a});
    }

    // 初始化 dist 数组
    memset(dist, 0x3f, sizeof(dist));

    // Dijkstra 初始化
    // 起点是 1 号点，时间可以是 0 (或者 k 的倍数)，初始模 k 为 0
    dist[1][0] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({1, 0});

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        int u = curr.u;
        int t = curr.time;
        int rem = t % k;

        if (vis[u][rem]) continue;
        vis[u][rem] = true;

        for (auto& edge : adj[u]) {
            int v = edge.v;
            int a = edge.a;

            // 计算通过这条边的时间
            // 我们需要找到一个时间 t_pass >= t 且 t_pass >= a
            // 且 t_pass % k == t % k (因为只能通过推迟起点的出发时间来等待，每次推迟 k)
            
            int t_pass = t;
            if (t_pass < a) {
                // 需要补足的时间差
                int diff = a - t_pass;
                // 向上取整 k 的倍数
                int count = (diff + k - 1) / k;
                t_pass += count * k;
            }

            int t_next = t_pass + 1;
            int rem_next = t_next % k;

            if (t_next < dist[v][rem_next]) {
                dist[v][rem_next] = t_next;
                pq.push({v, t_next});
            }
        }
    }

    // 目标是到达 n 号点，且时间 % k == 0
    if (dist[n][0] == INF) {
        cout << -1 << endl;
    } else {
        cout << dist[n][0] << endl;
    }

    return 0;
}

数据生成器 (Generator)

这个生成器会生成 1.in 到 20.in 以及对应的标准输出 1.out 到 20.out。 数据覆盖了题目描述中的所有特殊性质和边界情况。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <ctime>

using namespace std;

// ==========================================
// Part 1: Solution Logic (Solver)
// ==========================================
const int MAXN_SOL = 10005;
const int MAXK_SOL = 105;
const int INF_SOL = 0x3f3f3f3f;

struct Edge_Sol {
    int v, a;
};

struct Node_Sol {
    int u, time;
    bool operator>(const Node_Sol& other) const {
        return time > other.time;
    }
};

int dist_sol[MAXN_SOL][MAXK_SOL];
bool vis_sol[MAXN_SOL][MAXK_SOL];

int solve(int n, int m, int k, const vector<tuple<int, int, int>>& edges) {
    vector<vector<Edge_Sol>> adj(n + 1);
    for (const auto& e : edges) {
        adj[get<0>(e)].push_back({get<1>(e), get<2>(e)});
    }

    memset(dist_sol, 0x3f, sizeof(dist_sol));
    memset(vis_sol, 0, sizeof(vis_sol));

    dist_sol[1][0] = 0;
    priority_queue<Node_Sol, vector<Node_Sol>, greater<Node_Sol>> pq;
    pq.push({1, 0});

    while (!pq.empty()) {
        Node_Sol curr = pq.top();
        pq.pop();

        int u = curr.u;
        int t = curr.time;
        int rem = t % k;

        if (vis_sol[u][rem]) continue;
        vis_sol[u][rem] = true;

        for (auto& edge : adj[u]) {
            int v = edge.v;
            int a = edge.a;

            int t_pass = t;
            if (t_pass < a) {
                int diff = a - t_pass;
                int count = (diff + k - 1) / k;
                t_pass += count * k;
            }

            int t_next = t_pass + 1;
            int rem_next = t_next % k;

            if (t_next < dist_sol[v][rem_next]) {
                dist_sol[v][rem_next] = t_next;
                pq.push({v, t_next});
            }
        }
    }

    if (dist_sol[n][0] == INF_SOL) return -1;
    return dist_sol[n][0];
}

// ==========================================
// Part 2: Data Generator
// ==========================================

mt19937 rng(time(0));

int rand_int(int min, int max) {
    if (min > max) return min;
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

void generate_data(int id) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    ofstream fin(in_file);
    ofstream fout(out_file);

    int n, m, k;
    int max_a = 1000000;
    bool prop_a0 = false;
    bool prop_dag = false;

    // 根据测试点编号设定参数
    if (id <= 2) { // n<=10, m<=15, k<=100, a_i=0
        n = rand_int(5, 10);
        m = rand_int(n, 15);
        k = rand_int(1, 100);
        prop_a0 = true;
    } else if (id <= 5) { // n<=10, m<=15, k<=100, random a
        n = rand_int(5, 10);
        m = rand_int(n, 15);
        k = rand_int(1, 100);
    } else if (id <= 7) { // n<=10^4, m<=2*10^4, k=1, a_i=0
        n = rand_int(100, 10000);
        m = rand_int(n, 20000);
        k = 1;
        prop_a0 = true;
    } else if (id <= 10) { // n<=10^4, m<=2*10^4, k=1, random a
        n = rand_int(100, 10000);
        m = rand_int(n, 20000);
        k = 1;
    } else if (id <= 13) { // n<=10^4, m<=2*10^4, k<=100, a_i=0
        n = rand_int(100, 10000);
        m = rand_int(n, 20000);
        k = rand_int(80, 100);
        prop_a0 = true;
    } else if (id <= 15) { // n<=10^4, m<=2*10^4, k<=100, u<=v (DAG)
        n = rand_int(100, 10000);
        m = rand_int(n, 20000);
        k = rand_int(80, 100);
        prop_dag = true;
    } else { // 16-20: General
        n = rand_int(5000, 10000);
        m = rand_int(n, 20000);
        k = rand_int(80, 100);
    }

    vector<tuple<int, int, int>> edges;
    
    // 保证图一定程度上连通，至少包含一条 1->...->n 的链（防止大量 -1）
    // 随机生成一条主干路
    vector<int> p(n);
    for(int i=0; i<n; ++i) p[i] = i+1;
    // shuffle p[1...n-2] to randomize path, but keep 1 start and n end logic simple
    // 简单起见，直接构造一条链 1 -> x -> y -> ... -> n
    vector<int> chain;
    chain.push_back(1);
    vector<bool> in_chain(n + 1, false);
    in_chain[1] = true;
    in_chain[n] = true;
    
    int chain_len = rand_int(2, n); // 链长
    for (int i = 0; i < chain_len - 2; ++i) {
        int node = rand_int(2, n - 1);
        int tries = 0;
        while (in_chain[node] && tries < 10) {
            node = rand_int(2, n - 1);
            tries++;
        }
        if (!in_chain[node]) {
            chain.push_back(node);
            in_chain[node] = true;
        }
    }
    chain.push_back(n);

    // 添加链边
    for (size_t i = 0; i < chain.size() - 1; ++i) {
        int u = chain[i];
        int v = chain[i+1];
        if (prop_dag && u > v) swap(u, v);
        int a = prop_a0 ? 0 : rand_int(0, max_a);
        edges.emplace_back(u, v, a);
    }

    // 填充剩余边
    int current_m = edges.size();
    while (current_m < m) {
        int u = rand_int(1, n);
        int v = rand_int(1, n);
        if (u == v) continue; // 避免自环
        if (prop_dag && u > v) continue; // 保持 DAG 性质
        
        int a = prop_a0 ? 0 : rand_int(0, max_a);
        edges.emplace_back(u, v, a);
        current_m++;
    }

    // 输出 input
    fin << n << " " << m << " " << k << endl;
    for (const auto& e : edges) {
        fin << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << endl;
    }

    // 计算 output
    int ans = solve(n, m, k, edges);
    fout << ans << endl;

    fin.close();
    fout.close();
    cout << "Generated Test Point " << id << endl;
}

int main() {
    ios::sync_with_stdio(false);
    for (int i = 1; i <= 20; ++i) {
        generate_data(i);
    }
    cout << "All data generated." << endl;
    return 0;
}