【题目链接】
ybt 2101：【23CSPJ普及组】旅游巴士(bus)
洛谷 P9751 [CSP-J 2023] 旅游巴士
【题目考点】
1. 图论：求最短路Dijkstra, SPFA
2. 动态规划
3. 二分答案
4. 图论：广搜BFS
【解题思路】
解法1：Dijkstra堆优化
每个地点是一个顶点，每条道路是一条边，道路只能单向通行，该图是有向图。通过每条边用时都是1单位时间，那么该图是无权图。每条道路都有开放时刻a，也就是说对于每条边：该边的a时刻后，才存在，在a时刻前不存在。
该题问的是离开景区的最早时间，也就是到达顶点n的最早时间。
如果给定进入园区的时刻，即便每条边有开放时间的限制，我们依然可以通过求最短路算法（如BFS，Dijkstra，SPFA）得到从起点到终点的最短路径长度。但到达终点的时刻未必是k的倍数。
观察变量取值范围，看到 1 ≤ k ≤ 100 1\le k \le 100 1≤k≤100，这是本题的突破点。
要想使到达顶点n的时刻是k的倍数，那么到达前一个顶点的时刻一定应该满足模k等于k-1（除以k的余数是k-1），到达路径上再前一个顶点的时刻应该满足模k等于k-2。。。
因此到达某顶点的时刻模k的值也是我们的需要考虑的限制。
状态定义：
- 阶段：到达顶点i，到达该顶点的时间模k的值
- 决策：下一步走到哪个邻接点
- 策略：路径
- 策略集合：在k的整数倍时刻从起点出发到达顶点i的所有路径
- 条件：时刻最早
- 统计量：时刻
d p [ i ] [ j ] dp[i][j] dp[i][j]：在k的整数倍时刻从起点出发到达顶点i，到达顶点i的时刻模k等于j的最早时刻。
状态转移方程：
- 策略集合：在k的整数倍时刻从起点出发到达顶点i的所有路径
- 分割策略集合：根据到达顶点v的前一个顶点的情况分割策略集合
由于本题没有说明整个图是有向无环图，因此不能使用拓扑排序的方法。
每个状态都可能多次被更新，因此需要使用Dijkstra或SPFA算法，更新状态变量。
可以从顶点u走到下一个顶点v时，更新顶点v的状态。
假设在第0时刻从顶点出发，在 t t t时刻到达顶点u，边<u,v>的开放时间为 a a a
- 如果 t ≥ a t\ge a t≥a，通过顶点u到达顶点v的最早时刻 t m i n = t + 1 tmin = t+1 tmin=t+1。
- 如果 t < a t<a t<a，为了从顶点u通过边<u,v>走到顶点v，需要在入园前等待一段时间后再入园，入园时刻必须是 k k k的整数倍。（这个人在游玩时不能在任何位置停留，那么只能在入园前等待）
如果等待 k k k时间后再入园，走相同路径到达顶点u时的时刻就是 t + k t+k t+k
如果等待 2 k 2k 2k时间后再入园，走相同路径到达顶点u时的时刻就是 t + 2 k t+2k t+2k
如果等待 x k xk xk时间后再入园，走相同路径到达顶点u时的时刻就是 t + x k t+xk t+xk。希望到达顶点u时边<u,v>已开放，则需要满足不等式
t + x k ≥ a t+xk\ge a t+xk≥a，即 x ≥ a − t k x \ge \frac{a-t}{k} x≥ka−t， x x x最小为 ⌈ a − t k ⌉ \lceil \frac{a-t}{k} \rceil ⌈ka−t⌉。
因此如果想要通过<u,v>到达顶点v，那么到达顶点u的最早时刻为 t + ⌈ a − t k ⌉ k t+\lceil \frac{a-t}{k} \rceil k t+⌈ka−t⌉k
因此如果 t < a t<a t<a，通过顶点u到达顶点v的最早时刻为 t + ⌈ a − t k ⌉ k + 1 t+\lceil \frac{a-t}{k} \rceil k+1 t+⌈ka−t⌉k+1
因此存在一条到达顶点v的最早到达时刻为 t m i n tmin tmin的路径，使用 t m i n tmin tmin更新 d p [ v ] [ t m i n % k ] dp[v][tmin\%k] dp[v][tmin%k]。即如果 d p [ v ] [ t m i n % k ] > t m i n dp[v][tmin\%k]>tmin dp[v][tmin%k]>tmin，那么设 d p [ v ] [ t m i n % k ] = t m i n dp[v][tmin\%k]=tmin dp[v][tmin%k]=tmin。
具体实现
如果到达某个顶点的最早时刻发生更新，而后应该再更新到达其邻接点的最早时刻。
该过程可以使用Dijkstra堆优化算法完成，需要把达顶点v的最早到达时刻为 t m i n tmin tmin的路径加入到优先队列。
到达顶点n，最早到达时刻模k等于0的最早到达时刻 d p [ n ] [ 0 ] dp[n][0] dp[n][0]就是最终结果。
复杂度分析
每个顶点有k个状态，因此可以将每个顶点看作k个顶点，原来的每条边可以看作k条边，整个图变为有nk个顶点，mk条边的图。
已知Dijkstra堆优化的时间复杂度为 O ( m k ⋅ l o g ( m k ) ) O(mk\cdot log(mk)) O(mk⋅log(mk))，m最大是 2 ∗ 1 0 4 2*10^4 2∗104，k最大是100，该复杂度可以接受。
解法2：二分答案+bfs
可以反向思考，先通过二分答案确定到达终点n的时刻 t e te te，保证te是k的整数倍。
由于 a ≤ 1 0 6 a\le 10^6 a≤106，当开始时刻达到 1 0 6 10^6 106时，图中所有边都开放了。
边数 m ≤ 2 ∗ 1 0 4 m\le 2*10^4 m≤2∗104，假设在大约 1 0 6 10^6 106时刻出发，从顶点1到顶点n的路径需要经过所有的边，到达时刻不超过 1 0 7 10^7 107
由于k最大为100，我们可以二分到达时刻除以k的值，该值最小为0，最大值设大一点，就写 1 0 7 10^7 107，这样求出的 t e te te最小为0，最大不超过 1 0 9 10^9 109
判断解 t e te te是否满足条件：
建立原图的反图。从顶点n开始进行广搜。
如果搜索到顶点u时的时刻为t，u有邻接点v，在原图中，就是看在t-1时刻边<v,u>是否已开放，已知<v,u>的开放时间是a，如果 t − 1 ≥ a t-1\ge a t−1≥a，那么可以在原图中从顶点v经过<v,u>到达顶点u。
在反图中，也就是判断如果 t − 1 ≥ a t-1\ge a t−1≥a，那么边<u,v>已开放，可以在反图中从顶点u访问到邻接点v。
看是否存在到达顶点1的，到达时刻是k的整数倍的路径。
设vis数组，需要同时考虑到达顶点i，以及到达该顶点的时刻模k的值。
设vis[i][j]表示到达顶点i，且到达时刻模k等于j的情况是否已发生。
因为在该问题的广搜的过程中，到达顶点的时刻是不断减少的，如果已经发生过到达顶点i且时刻模k等于j的情况，设该时刻是 t 1 t_1 t1。再次发生到达顶点i且时刻模k等于j时的时刻是 t 2 t_2 t2，则一定有 t 1 > t 2 t_1>t_2 t1>t2。
如果从顶点i，时刻 t 1 t_1 t1出发通过一条路径到达顶点1，到达顶点1的时刻模k不等于0。那么从顶点i，时刻 t 2 t_2 t2出发经过相同的路径到达顶点1，到达顶点1的时刻模k的值和上面的情况中的值一定是一样的，也不为0。
因此如果已经发生过到达顶点i，到达时刻模k等于j的情况，就不用考虑后面出现的到达顶点i，到达时刻模k等于j的情况。
在反图进行广搜的过程中，对于每个出队的顶点u及到达u的时刻t
遍历u的邻接点v，到达顶点v的时刻为 t − 1 t-1 t−1，<u,v>的开放时间为a
- 如果 t − 1 < a t-1<a t−1<a，则在原图中到达v时<v,u>边未开放，略过这种情况。
- 如果到达顶点v，到达时刻模k等于 ( t − 1 ) % k (t-1)\%k (t−1)%k的情况已经发生过，则略过。
不满足以上情况，才要访问顶点v：
如果顶点v就是顶点1，且到达的时刻 t − 1 t-1 t−1是k的倍数，则找到了一个可行的解，答案出园时刻 t e te te满足条件。
而后存在到达顶点v，时刻为 t − 1 t-1 t−1的情况，将该情况加入队列。并标记到达顶点v，时刻模k等于 ( t − 1 ) % k (t-1)\%k (t−1)%k的情况已存在。
如果广搜结束后也没有找到可行的解，则出园时刻 t e te te不满足条件，返回假。
【题解代码】
解法1：Dijkstra堆优化算法+动态规划
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, K = 100, INF = 0x3f3f3f3f;
struct Path
{int u, t;//存在到达顶点u，时刻为t的路径 bool operator < (const Path &b) const{return b.t < t;//时刻t更小更优先 }
};
struct Edge
{int v, a;
};
int n, m, k, dp[N][K];//在k的整数倍时刻从起点出发到达顶点i，到达顶点i的时刻模k等于j的最早时刻。
vector<Edge> edge[N];
int divCeil(int a, int b)//ceil(a/b)
{return (a-1)/b+1;
}
void dijkstra()
{priority_queue<Path> pq;memset(dp, 0x3f, sizeof(dp));//求最短路径，先将状态设为无穷 dp[1][0] = 0;//到达顶点1（起点），到达时刻模k为0的最早时刻为0pq.push(Path{1, 0});while(!pq.empty()){int u = pq.top().u, t = pq.top().t;pq.pop();for(Edge e : edge[u]){int v = e.v, a = e.a, tmin;//tmin：想要从u通过<u,v>，到达v的最早时刻 if(t >= a)tmin = t+1;elsetmin = t+1+divCeil(a-t, k)*k;if(dp[v][tmin%k] > tmin){dp[v][tmin%k] = tmin;pq.push(Path{v, tmin});}}}
}
int main()
{int u, v, a;cin >> n >> m >> k;for(int i = 1; i <= m; ++i){cin >> u >> v >> a;edge[u].push_back(Edge{v, a});}dijkstra();cout << (dp[n][0] == INF ? -1 : dp[n][0]);return 0;
}
解法2：二分答案+bfs
#include<bits/stdc++.h>
using namespace std;
const int N = 10005, K = 100, INF = 0x3f3f3f3f;
struct Path
{int u, t;//到达顶点u，到达时刻t
};
struct Edge
{int v, a;
};
int n, m, k;
vector<Edge> rg[N];//反图
bool vis[N][K];
bool check(int te)//判断到达时刻为te时，是否存在从n到1的，到达顶点1的时刻模k等于0的路径。
{memset(vis, 0, sizeof(vis));queue<Path> que;vis[n][te%k] = true;que.push(Path{n, te});while(!que.empty()){int u = que.front().u, t = que.front().t;que.pop();for(Edge e : rg[u]){int v = e.v, a = e.a;if(t-1 >= a && !vis[v][(t-1)%k])//到顶点v时<v,u>已开放，同时现在没有在访问时刻模k等于(t-1)%k时访问顶点v {if(v == 1 && (t-1)%k == 0)//找到解，te满足条件 return true;vis[v][(t-1)%k] = true;que.push(Path{v, t-1});}}}return false;//te不满足条件
}
int main()
{int u, v, a;cin >> n >> m >> k;for(int i = 1; i <= m; ++i){cin >> u >> v >> a;rg[v].push_back(Edge{u, a});//建反图}int l = 0, r = 1e7; while(l < r){int mid = (l+r)/2;if(check(mid*k))//答案是mid*k，mid*k最大为1e9r = mid;elsel = mid+1; }if(check(l*k))//二分得到的答案也未必是满足条件的，需要再判断一下 cout << l*k;elsecout << -1;return 0;
}
