难度 | 算法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 });}}}
}
分层图在哪里?
未完待续......