【CSP2023-J组-04】旅游巴士

**BFS+DP**
道路的时间是限制，但不会计入到答案中，因为它只是起到了能不能走。
所以答案有两部分组成：**出发的时间**和**经过的时间**。
因为出发的时间必须是k的倍数，所以经过的时间也要k的倍数。
而出发的时间要根据**道路开放时间**进行变化，即如果遇到道路还没开放，则需要**推迟出发时间**且必须是**k的倍数**。
为了求出最短时间，那么需要记录到每个顶点的时间，**不同的线路**走到同一个顶点如果**时间相同**（此时间只考虑经过道路所花的时间），则保留最优解（虽然走到时间相同，但出发时间可能不同，选择最优的）。路线可能很长，把行走时间看成状态的话，状态会很多，因为题目要求的是$k$的倍数，所以到一个顶点的状态可以看成$0$~$k-1$种，这样也能表示顶点的所有状态。
所以不妨设$dp[i][j]$，$i$表示顶点编号,$j$表示行走时间（不考虑出发时间）模$k$的余数的最优解。
BFS部分代码
```
	memset(f,0x5f,sizeof f);
	q.push({1,0,0}); //结构体分别为顶点编号、余数、行走时间
	dp[1][0] = 0;
	while(q.size()){
		bus t = q.top();
		q.pop();
		for(int i = head[t.id]; i; i = e[i].next){
			int y = e[i].to;
			int w = e[i].w;
			int newc = (t.c+1)%k;  //计算新的状态（余数）
			int s = dp[t.id][t.c]; //上一位置的最优解
			if(s<w) s+=(w-s+k-1)/k*k; //是否要推迟出发时间，w为道路开放时间
			if(dp[y][newc]>s+1){ //转移方程，到达新顶点的状态，不能忘记走过去需要消耗1单位时间
				dp[y][newc]=s+1;  //状态更新
				q.push({y,newc,s+1}); //入队
			}
		}
		
	}
```
q为优先队列，结构体内重载operator，根据总的花费时间来比较（即第3个字段)，花费时间少，优先出队。
答案就是$d[n][0]$。
(w-s+k-1)/k是进一的快速计算方法，w-s表示相差多少时间，加k-1，能保证余1的时候就能进一。

Merlin's Blog

Navigation

Recent Posts

Friend Links