NOI2025_机器人

不是，近 5 年 NOI 从来没考过绿吧，不会吧？

形式化题面如下：

给定一个有向图，包含$n$ 个节点和$m$ 条有向边。边有长度。对于每个节点$x$，其出边被编号为$1\to d_{x}$（$d_{x}$ 是出边数量）。从$1$ 号点出发，初始有一个变量$p=1$，按以下规则移动：

• 若当前位于节点$x$ 且$p\le d_{x}$，则走$x$ 的第$p$ 条边，移动到相邻节点$y$。花费为边的长度。
• 修改参数$p$：
  • 若$p<k$，则令$p\leftarrow p+1$，花费为$v_{p}$。
  • 若$p>1$，则令$p\leftarrow p-1$，花费为$w_{p}$。

求$1\to i$ 的最小花费，若无法到达输出$-1$。

一眼分层图，题目转化为建$k$ 层的有向图，每次跳不同层要花费规则上指定的代价，求单源最短路跑 Dijkstra。但是空间复杂度是$O(nk)$，且时间复杂度为$O(nk\log nk)$，无法通过。

我们设分层图状态为$(u,p)$ 表示在第$u$ 点，参数为$p$。

考虑优化，首先一个关键观察就是当$d_{x}<p$ 的时候是没有任何卵用的，$(u,p)$ 是无效状态。我们没必要建这么多图，考虑每一层就建$d_x$ 层就可以啦。

接下来还有一个很难受的过程就是修改参数，考虑这个怎么优化，花费和$p$ 有关，一个不难观察到的地方每次增减量是$1$，考虑前缀和优化修改参数这一过程，这样复杂度从$O(k)\to O(1)$。这一部分我们可以通过 map 或哈希表实现，时间复杂度$O(n \log n \log k)\to O(n \log n)$。

代码数据出来补一下？