信息学奥赛一本通 2101：【23CSPJ普及组】旅游巴士(bus) | 洛谷 P9751 [CSP-J 2023] 旅游巴士

【题目链接】

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\le k\le 100$，这是本题的突破点。
要想使到达顶点n的时刻是k的倍数，那么到达前一个顶点的时刻一定应该满足模k等于k-1（除以k的余数是k-1），到达路径上再前一个顶点的时刻应该满足模k等于k-2。。。
因此到达某顶点的时刻模k的值也是我们的需要考虑的限制。

状态定义：

• 阶段：到达顶点i，到达该顶点的时间模k的值
• 决策：下一步走到哪个邻接点
• 策略：路径
• 策略集合：在k的整数倍时刻从起点出发到达顶点i的所有路径
• 条件：时刻最早
• 统计量：时刻

$dp[i][j]$：在k的整数倍时刻从起点出发到达顶点i，到达顶点i的时刻模k等于j的最早时刻。

状态转移方程：

• 策略集合：在k的整数倍时刻从起点出发到达顶点i的所有路径
• 分割策略集合：根据到达顶点v的前一个顶点的情况分割策略集合

由于本题没有说明整个图是有向无环图，因此不能使用拓扑排序的方法。
每个状态都可能多次被更新，因此需要使用Dijkstra或SPFA算法，更新状态变量。
可以从顶点u走到下一个顶点v时，更新顶点v的状态。
假设在第0时刻从顶点出发，在$t$时刻到达顶点u，边<u,v>的开放时间为$a$

• 如果$t\ge a$，通过顶点u到达顶点v的最早时刻$tmin=t+1$。
• 如果$t<a$，为了从顶点u通过边<u,v>走到顶点v，需要在入园前等待一段时间后再入园，入园时刻必须是$k$的整数倍。（这个人在游玩时不能在任何位置停留，那么只能在入园前等待）
  如果等待$k$时间后再入园，走相同路径到达顶点u时的时刻就是$t+k$
  如果等待$2k$时间后再入园，走相同路径到达顶点u时的时刻就是$t+2k$
  如果等待$xk$时间后再入园，走相同路径到达顶点u时的时刻就是$t+xk$。希望到达顶点u时边<u,v>已开放，则需要满足不等式
  $t+xk\ge a$，即$x\ge \frac{a-t}{k}$，$x$最小为$\lceil \frac{a-t}{k}\rceil$。
  因此如果想要通过<u,v>到达顶点v，那么到达顶点u的最早时刻为$t+\lceil \frac{a-t}{k}\rceil k$
  因此如果$t<a$，通过顶点u到达顶点v的最早时刻为$t+\lceil \frac{a-t}{k}\rceil k+1$

因此存在一条到达顶点v的最早到达时刻为$tmin$的路径，使用$tmin$更新$dp[v][tmin\%k]$。即如果$dp[v][tmin\%k]>tmin$，那么设$dp[v][tmin\%k]=tmin$。

具体实现

如果到达某个顶点的最早时刻发生更新，而后应该再更新到达其邻接点的最早时刻。
该过程可以使用Dijkstra堆优化算法完成，需要把达顶点v的最早到达时刻为$tmin$的路径加入到优先队列。
到达顶点n，最早到达时刻模k等于0的最早到达时刻$dp[n][0]$就是最终结果。

复杂度分析

每个顶点有k个状态，因此可以将每个顶点看作k个顶点，原来的每条边可以看作k条边，整个图变为有nk个顶点，mk条边的图。
已知Dijkstra堆优化的时间复杂度为$O(mk\cdot log(mk))$，m最大是$2\ast 10^4$，k最大是100，该复杂度可以接受。

解法2：二分答案+bfs

可以反向思考，先通过二分答案确定到达终点n的时刻$te$，保证te是k的整数倍。
由于$a\le 10^6$，当开始时刻达到$10^6$时，图中所有边都开放了。
边数$m\le 2\ast 10^4$，假设在大约$10^6$时刻出发，从顶点1到顶点n的路径需要经过所有的边，到达时刻不超过$10^7$
由于k最大为100，我们可以二分到达时刻除以k的值，该值最小为0，最大值设大一点，就写$10^7$，这样求出的$te$最小为0，最大不超过$10^9$
判断解$te$是否满足条件：
建立原图的反图。从顶点n开始进行广搜。
如果搜索到顶点u时的时刻为t，u有邻接点v，在原图中，就是看在t-1时刻边<v,u>是否已开放，已知<v,u>的开放时间是a，如果$t-1\ge a$，那么可以在原图中从顶点v经过<v,u>到达顶点u。
在反图中，也就是判断如果$t-1\ge a$，那么边<u,v>已开放，可以在反图中从顶点u访问到邻接点v。
看是否存在到达顶点1的，到达时刻是k的整数倍的路径。
设vis数组，需要同时考虑到达顶点i，以及到达该顶点的时刻模k的值。
设vis[i][j]表示到达顶点i，且到达时刻模k等于j的情况是否已发生。

因为在该问题的广搜的过程中，到达顶点的时刻是不断减少的，如果已经发生过到达顶点i且时刻模k等于j的情况，设该时刻是$t_1$。再次发生到达顶点i且时刻模k等于j时的时刻是$t_2$，则一定有$t_1>t_2$。
如果从顶点i，时刻$t_1$出发通过一条路径到达顶点1，到达顶点1的时刻模k不等于0。那么从顶点i，时刻$t_2$出发经过相同的路径到达顶点1，到达顶点1的时刻模k的值和上面的情况中的值一定是一样的，也不为0。
因此如果已经发生过到达顶点i，到达时刻模k等于j的情况，就不用考虑后面出现的到达顶点i，到达时刻模k等于j的情况。

在反图进行广搜的过程中，对于每个出队的顶点u及到达u的时刻t
遍历u的邻接点v，到达顶点v的时刻为$t-1$，<u,v>的开放时间为a

• 如果$t-1<a$，则在原图中到达v时<v,u>边未开放，略过这种情况。
• 如果到达顶点v，到达时刻模k等于$(t-1)\%k$的情况已经发生过，则略过。

不满足以上情况，才要访问顶点v：
如果顶点v就是顶点1，且到达的时刻$t-1$是k的倍数，则找到了一个可行的解，答案出园时刻$te$满足条件。
而后存在到达顶点v，时刻为$t-1$的情况，将该情况加入队列。并标记到达顶点v，时刻模k等于$(t-1)\%k$的情况已存在。
如果广搜结束后也没有找到可行的解，则出园时刻$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的最早时刻为0
	pq.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;
			else
			 	tmin = 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最大为1e9
			r = mid;
		else
			l = mid+1; 
	}
	if(check(l*k))//二分得到的答案也未必是满足条件的，需要再判断一下 
		cout << l*k;
	else
		cout << -1;
	return 0;
}