题目大意

给定一个 $n$ 个点 $m$ 条边的无向图，每条边有 $k$ 个权值 $a_{i,j}$。从点 $1$ 出发，在 $d$ 天内到达点 $n$（每天走一条边）。经过一条边时，可以选择将其某些类型的权值"收集"到最终答案中。要求求出 $k$ 个类型的最大字典序序列。

核心思路

1. 问题转化

• 对于每种剑类型 $j$，我们要在保证前 $j-1$ 种剑价值最大的前提下，最大化第 $j$ 种剑的价值
• 这相当于按优先级分层求解：先确定类型 $1$ 的最大值，再固定这个值去求类型 $2$ 的最大值，依此类推

2. 关键观察

对于第 $u$ 种剑，我们关心的是：

• 是否存在一条从 $1$ 到 $n$ 的路径，长度 $\leq D$
• 路径上包含至少一条边，其 $a_{e,u}$ 等于我们考虑的候选值 $ans$
• 并且这条路径不会降低前 $u-1$ 种剑已经确定的最大值

3. 状态压缩与 BFS

• 用状态压缩记录前 $u-1$ 种剑的收集情况
• 定义 $ds[x][S]$：从点 $1$ 到点 $x$，收集了状态 $S$（表示前 $u-1$ 种剑的哪些已经按最大值收集）的最短天数
• 定义 $dt[x][S]$：从点 $n$ 到点 $x$，收集了状态 $S$ 的最短天数

4. 判定公式

对于候选值 $ans$ 和边 $e=(x,y)$，检查是否存在状态分割：

其中：

• $S$ 和 $T$ 是互补的状态分割
• 要保证边 $e$ 上能收集到当前候选值 $ans$
• 并且不破坏前 $u-1$ 种剑的已确定最大值

5. 算法流程

对每个剑类型 $u$ 依次处理：

1. 用 BFS 预处理 $ds$ 和 $dt$
2. 二分或扫描确定当前类型的最大值 $ans$
3. 标记所有能达到该最大值的边
4. 输出结果，继续处理下一类型

复杂度分析

• 状态数：$O(n \cdot 2^k)$
• 对每个类型进行两次 BFS：$O(m \cdot 2^k)$
• 总复杂度：$O(k \cdot m \cdot 2^k)$，在 $k \leq 10$ 时可接受

这种方法通过分层处理和状态压缩，巧妙地解决了字典序优化问题。