| 难度 | 算法s | 日期 | 题目链接 |
|---|---|---|---|
| 普及+/提高 | 分层图、Dijikstra | 2025-07-19 | https://luogu.com.cn/problem/P9751 |
P9751 [CSP-J 2023] 旅游巴士
这道题在我的任务列表里面很久了。考场上看到它已经是很久以前的事咯。
题意简述
-
给一个 \(n\) 个节点，\(m\) 条边的有向图，节点编号 \(1\to n\)。规定 \(1\) 为入口，\(n\) 为出口。从景区开放为时刻 \(0\)，每条边有一个开放时间 \(a\)，只有在时间 \(t\ge a\) 时才可以经过这条边。经过每条边总是需要 \(1\) 单位时间。
-
给定一个发车间隔 \(k\)，从时刻 \(0\) 开始每隔 \(k\) 单位时间会有一辆大巴到达入口，同时也会有一辆大巴从出口离开。（ps：第一辆到景区的大巴会在时刻 \(0\) 抵达）
-
问：不能在路上停留（包括起点和终点，但是可以选择搭乘哪一辆大巴到达入口），是否有可能到达出口时恰能乘坐大巴离开？如果能，最早离开的时间？
也就是说：能不能恰好在 \(k\) 时间内从入口走到出口？求最早离开的时间。（没有方案输出 \(-1\)）
范围：\(2\le n\le10^4\)，\(1\le m\le 2\times10^4\)，\(1\le k\le 100\)，\(0\le a_i\le10^6\)。
某种意义上的最短路 & DP
题目要求最早离开，也就是求最短路咯。但是有一点不同：我们要保证到达终点的时间是 \(k\) 的倍数。这怎么办呢？
-
如果是一般的最短路，对于每个节点 \(u\)，我们会记录最早到达 \(u\) 的时间，不妨记为 \(\min t(u)\)。
-
但是我们这里要 “凑整”，所以我们要记录一个数组 \(T(u,j)\)，定义为：\(min_{t(u)}\{t(u)\equiv j\pmod{k}\}\)。也就是我们把每个从源点到 \(u\) 的路径长度对 \(k\) 取模，分别维护余数为 \(j\) 的路径的长度最小值，记为 \(T(u,j)\)。
-
显然 \(T(n,0)\) 即为答案。
我们考虑一下如何转移这个状态。假设我们到达节点 \(u\) 时花费时间为 \(t(u)\)，边 \((u,v)\) 的开放时间是 \(a\)：
-
初始化所有 \(T(u,j)=+\infty\)。
-
如果 \(t(u)\ge a\)，则可以通过 \((u,v)\)。那么记 \(j=[t(u)+1]\bmod k\)， \(T(v,j)=\min \{T(u,j),t(u)+1\}\)。
-
如果 \(t(u)\lt a\)，则我们至少要等待（乘坐下一趟大巴） ：
\[\lceil\cfrac{a-t(u)}{k}\rceil\times k \]单位时间才能通过 \((u,v)\)。那么：
\[j=[t(u)+\lceil\cfrac{a-t(u)}{k}\rceil\times k+1]\bmod k,\newline T(v,j)=\min\{T(v,j),t(u)+\lceil\cfrac{a-t(u)}{k}\rceil\times k+1\}. \]
转移方程就这？这能对吗？没事我们再加一点 Dijkstra。
超时空 Dijkstra
const int MAXN = 1e4, MAXK = 100;
int t[MAXN + 1][MAXK], vis[MAXN + 1];
struct State { // 不知道起什么名字，总之就是 (u, j)int u, j;bool operator<(const State& another) const {return t[u][j] > t[another.u][another.j];}
};
void dijkstra() {// 必要的初始化// 第一次的时候初始化错了，下面的for不能直接从2开始，因为一开始t[1][j] (j>0) 都是inf（之后有可能又回到起点！！）for (int i = 1; i <= n; i++) {for (int j = 0; j < k; j++) t[i][j] = INT_MAX;}t[1][0] = 0;priority_queue<State> q;q.push({ 1, 0 });State cur;int curt; // 当前状态的时间int j, wait;while (not q.empty()) {cur = q.top(), q.pop();if (vis[cur.u][cur.j]) continue;vis[cur.u][cur.j] = true;curt = t[cur.u][cur.j];for (int e = head[cur.u]; e; e = edges[e].nxt) {if (curt >= edges[e].open) {j = (curt + 1) % k;t[edges[e].to][j] = min(t[edges[e].to][j], curt + 1);q.push({ edges[e].to, j });} else {wait = ceil(float(edges[e].open - curt) / k) * k;j = (curt + wait + 1) % k;t[edges[e].to][j] = min(t[edges[e].to][j], curt + wait + 1);q.push({ edges[e].to, j });}}}
}
分层图在哪里？
未完待续......