概是我太蒻了吧，大部分题解我不是很懂。
就是一个改版的最短路。由于一单位时间走一个距离单位，所以距离和时间等价。设 \(dis_{i, j}\) 代表到了 \(i\) 点，距离模上 \(k\) 是 \(j\) 的距离最小值。
先不管开放时间的限制。然后对于一个点，所有他可到达的点都可以如此更新。
设 \(nxt = (dis_{s, j} + 1) \mod k\)。
\(dis_{to,nxt} = \min (dis_{s, j} + 1)\)
这个时候考虑限制的问题。
我们如果想走一条路，但是路的时间限制没到，那么我们就可以等下一班车，让时间凭空增加 \(k\)，直到大于路的时间限制。
显然你每次增加 \(k\)，在模 \(k\) 的意义下 \(j\) 是不会改变的，那 \(nxt\) 也不会改变。
所以，如果路径的限制即 \(lim_i\) 大于 \(dis_{s, j}\)，我们就如此更新。
\(dis_{to, nxt} = \min (dis_{s, j} + \lceil\frac{lim_i - dis_{s, j}}{k}\rceil \times k)\)
这样就可以在不改变 \(j\) 和 \(nxt\) 的情况下合法的更新。
然后就做完了。其他就是 SPFA 的板子。
我试了一下 BFS。有一组测试数据跑出了 59 秒好成绩。因此最好还是 SPFA 或 dijkstra。
#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define rep_(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
namespace Kx {constexpr int N = 1e4 + 5;int dis[N][105];int n, m, k, cnt, head[N];struct edge {int to, nxt, lim;} e[N << 1];inline void add(int u, int v, int l) {e[++cnt].to = v;e[cnt].nxt = head[u];e[cnt].lim = l;head[u] = cnt;}void bfs() {bool vis[N] = {};memset(dis, 0x3f, sizeof dis);dis[1][0] = 0;queue<int> q;q.push(1);vis[1] = true;while(!q.empty()) {int s = q.front();q.pop();vis[s] = false;for(register int i = head[s]; i; i = e[i].nxt) {rep(j, 0, k - 1) {int add = 0;if(dis[s][j] < e[i].lim) {add = (int)ceil((e[i].lim - dis[s][j]) * 1.0 / k) * k;}if(dis[s][j] + add + 1 < dis[e[i].to][(j + 1) % k]) {dis[e[i].to][(j + 1) % k] = dis[s][j] + add + 1;if(vis[e[i].to]) {continue;}q.push(e[i].to);vis[e[i].to] = true;}}}}}void main() {// freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);cin >> n >> m >> k;rep(i, 1, m) {int u, v, l; cin >> u >> v >> l;add(u, v, l);}bfs();if(dis[n][0] == 0x3f3f3f3f) {cout << -1 << '\n';}else {cout << dis[n][0];}}
}
int main() {Kx :: main();return 0;
}