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;
}