代码：

#include <bits/stdc++.h>
using namespace std;

int n, m, k, x, y, z, front, rear;
long long f[10006][101];
struct Edge {
	int to, l;
	long long z;
};
Edge q[3000001];
vector<Edge> edges[10001];

long long check(long long t) { // 该函数实现了从 t 时刻出发，到达终点的最短路径（不可能就是 -1）
	memset(f, 255, sizeof(f));
	f[1][0] = t;
	q[front = rear = 1] = {1, 0, t};
	while (rear + 1 != front) {
		Edge fx = q[front++];
		for (auto i : edges[fx.to]) {
			if (f[i.to][(fx.l + 1) % k] == -1 && fx.z >= i.l) {
				f[i.to][(fx.l + 1) % k] = f[fx.to][fx.l] + 1;
				q[++rear] = {i.to, (fx.l + 1) % k, fx.z + 1};
			}
		}
	}
	if (f[n][0] != -1) {
		return f[n][0];
	} else return -1;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (m--) {
		scanf("%d%d%d", &x, &y, &z);
		edges[x].push_back({y, z, 0});
	}
	long long l = 0, r = 2000000;
	long long ans = LONG_LONG_MAX;
	long long tmp = check(0);
	if (tmp != -1) ans = tmp;
	while (l + 1 != r) {
		long long mid = (l + r) / 2;
		long long res = check(mid * k);
		if (res != -1) {
			ans = min(ans, res);
			r = mid;
		} else {
			l = mid;
		}
	}
	if (ans == LONG_LONG_MAX) puts("-1");
	else printf("%lld\n", ans);
	return 0;
}

WA on #19, #20。

应该是没有问题的啊，因为开始时间越往后，可以经过的边就越多，所以，二分的上界大于 $\max a_i$ 所有边就都可以经过，不会有任何问题。

况且 check 传参传的是 mid * k，按道理来说更没有问题。

求解答QAQ