原题链接：https://www.luogu.com.cn/problem/P9751
题意解读：
在有向图中（每条边的权值是可通过的最早时间，通过每条边所用的时间是1，也可以认为每条边的路径长度是1），在某个k的整数倍时间点start出发，从1号点出发，计算到达n点的最短路径dist，使得dist%k==0（因为从起点出发和终点发车的时间都是k的整数倍，路径长度也一定是k的整数倍），计算到达终点的时间end=start+dist的最小值。
样例模拟：
关于本题的“骗分”方案，请移步之前的文章CSP-J 2023 T4 旅游巴士（CSP-J考纲范围内的解法：BFS+二分），本文主要针对正解用容易理解的邻接表重新写一下。
解题思路：
如果想到了最短路，每条边路径长度相同，那么首先会想到BFS，正如[CSP-J2019] 加工零件中所介绍过的，在用BFS计算起点到终点的普通最短路径时，如果终点只能走一次，那么最短路径长度也是唯一的，但如果每个点可以不止走一次，那么到终点的路径也会有多种。
本题要求取最短的那一个路径dist，使得dist%k==0，因为普通最短路不一定能整除k，所以计算起点到终点的路径时要把%k的所有路径长度都存储下来，对于一个节点是否能重复走，需要依据路径长度%k是否已经走到过。通过一个二维数组dist[N][K]即可搞定。
由于每个节点都有一个最早能通过的时间，在BFS过程中，下一个节点能不能走，除了根据路径长度%k是否已经存在，还要判断当前的时间是否>=节点最早能通过时间，当前的时间就是出发时间+已经走过的路径。
下面梳理一下截止目前的解题流程：
1、枚举出发时间点start：0, 3, 6 ...... 直到最大的边权值（最早出发时间）
2、BFS计算起点到终点最短的模k为0的路径dist
3、如果路径存在，则更新到终点时间的最小值，ans = min(ans, start+dist)
4、如果路径不存在，输出-1
分析一下时间复杂度，出发时间最大值是10^6，节点和边数10^4，总的时间复杂度在10^10/3,约是O(10^9)规模
如何优化？BFS不能省，那么枚举出发时间点是否可以更快？想到了二分，下面分析一下是否具备单调性：
如果出发时间越大，显然受限制的节点越少，能走出一个最短路模k为0的路径可能性越高。
所以可以针对出发时间进行二分，找一个最小的出发时间，使得能走出最短路模k为0，然后更新到达终点时间的最小值。
但是，二分起点得到的终点并不是单调的，起点大肯定能走出模k为0的最短路，但起点最小不代表到达终点时间的时间也最小！
因此，更合理的方法是二分到达终点的最小时间，反向建图，bfs得到一个到起点的模k为0的时间。
100分代码：
#include <bits/stdc++.h>
using namespace std;const int N = 10005, K = 105;struct gnode
{int v; //边的终点int a; //边的权值，最早可通过时间
};
vector<gnode> g[N];
int dist[N][K]; //dist[i][j]表示从起点到i的最短的%k=j的路径
int n, m, k, ans = INT_MAX;struct qnode
{int u; //节点int d; //u节点距离起点路径长度
};//终点从end开始，通过bfs能否找到到起点时间%k=0的路径
bool bfs(int end)
{memset(dist, -1, sizeof(dist));queue<qnode> q;q.push({n, end});dist[n][0] = end;while(q.size()){qnode from = q.front(); q.pop();int u = from.u;for(gnode to : g[u]){int v = to.v;int d = from.d - 1; //到下一个点的时间是上一个点的时间-1if(dist[v][d % k] == -1 && d >= to.a) //如果到v的时间%k没有到过，且时间允许{q.push({v, d});dist[v][d % k] = d;}}}return dist[1][0] != -1;
}int main()
{cin >> n >> m >> k;int u, v, a;while(m--){cin >> u >> v >> a;g[v].push_back({u, a}); //反向建图}int l = 1, r = 2000000, ans = -1; //r取值2000000防止k*mid超intwhile(l <= r){int mid = (l + r) >> 1; //二分到达终点时间k*midif(bfs(k * mid)) ans = k * mid, r = mid - 1;else l = mid + 1;}cout << ans;return 0;
}
