题意：在一个有向图内，寻找出发时间和结束时间都为 k 的非负整数倍，且经过一条路的时间不早于这条路的边权 a[i] 的最小出发时间和结束时间。 特殊性质1：a[i] = 0，即不需考虑路上边权。 特殊性质2：u[i] <= v[i]，即除自己可以到达自己外，不会存在编号大于自己的节点可以到达自己的情况。 特殊性质3：k <= 1，即可以从任意时刻出发和到达。 注：可能存在自己到达自己的情况。 首先，当特殊性质1和特殊性质3结合，可以直接进行搜索。 输出 -1 可以得到 CCF 施舍的 5 分。 暴力搜索点 1 ~ 5，定义 vis[x][y] 为当前点为 x 时，到达该点时间 % k = y 是否到达过，复杂度 O(nk)。 对于点 6 ~ 7，相当于直接寻找最短路，复杂度 O(n)。 正解： 分析时间复杂度，显然只有 O(nk) 或 O(mk) 及以下才能过。 vis 定义同点 1 ~ 5。定义 dis[i][j] 表示在从点 1 出发到达点 i 时当前时间 % k = j 的最短距离。 考虑使用 BFS 或 DFS，调用参数为当前时间和当前点。 相比于普通最短路需要增加用优先队列维护，保证使当前时间最小的点处于最前。 对于开放时间，若当前时间大于等于开放时间直接无视，否则将出发时间推迟 k 的倍数次直到道路开放（即在当地等待了相同时间）。 更新 dis[nown][(nowt + 1) % k]，使其取最小值，若不需要更新，则这个状态将走过的路程已有更优解，跳过。 输出答案，若 vis[n][0] = 0，则没有对应路径，输出 -1，否则输出 dis[n][0]（当时间可以完全被整除时到达 n 的最短时间）。 AC：