P9751 [CSP-J 2023] 旅游巴士 题解

思路

首先，举一个例子，假如说 小Z 到了入口，但是没到时间，所以没法进去，该怎么办?

当然是等 $k$ 个时间单位呀.

除此之外，像到了其他景区，但是还没开门怎么办 ? 继续等 $k$ 的非负整数倍时间呀.

知道这个后，我们先定义状态 $f_{i,j}$，表示到达点 $i$ 时，路径长度(即时间) $mod$ $k$ 的最早时间.

目标：$f_{n,0}$.

为什么要取模呢? 因为这样不仅可以方便计算，而且题面中说到，到达和离开景区的时间均要是 $k$ 的非负整数倍数.所以当 $j=0$ 时，就说明是 $k$ 的倍数了.

转移

显然，这题可以使用最短路，我们在求最短路的同时进行转移.关于最短路算法，建议选择优先队列优化过后的$Dijkstra.$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

int n, m, k;
int f[10004][102]; // f[i][j]表示到点i，长度%k余数为j的最早时间

struct q{
	int id, mod, cost; // 节点编号，j，时间
	bool friend operator < (q a, q b) { // 重载小于运算符
		return a.cost > b.cost;
	}
}; 

struct node {
	int v, w;
};

int vis[10004][102];
vector<node> g[10004]; // vector 存图
priority_queue<q> pq; // 优先队列

void dijkstra() {
	pq.push((q){1, 0, 0}); // 最开始的元素
	while (!pq.empty()) {
		q h = pq.top();
		pq.pop();
		int u = h.id, j = h.mod, cost = h.cost;
        // 没有被访问过，更新 f[u][j]
		if (!vis[u][j]) f[u][j] = cost, vis[u][j] = 1;
		else continue;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i].v, w = g[u][i].w;
			int t = f[u][j];
			while (t < w) t += k; // 还没有开门，就继续等
			if (t + 1 < f[v][(j+1)%k]) // 更早的时间
				pq.push((q){v, (j+1)%k, t + 1}); // 放入优先队列
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back((node){v, w});
	}
	memset(f, 0x3f, sizeof(f)); // 初始化，较大的初值
	dijkstra();
	if (f[n][0] != 0x3f3f3f3f) printf("%d", f[n][0]); // 不是初值，说明可以到达
	else printf("-1");
	return 0;
}