题目理解

Bajtek 需要从学校（路口 $1$）回家（路口 $n$），可以乘坐公交车，但最多只能换乘 $k$ 次。每条公交线路有固定的发车时间表和路线。我们需要找到他最早能到家的时间。

算法思路

核心思想：分层图 + 动态规划

这个问题可以看作是在一个带有时间约束的公交网络中最短路问题，但由于公交车的发车时间有周期性，直接使用传统最短路算法比较困难。

关键数据结构

1. 道路网络：使用哈希表 E 存储路口间的通行时间
2. 公交线路：
   • bus[i] 存储第 $i$ 条线路的站点序列和累计时间
   • obus[x] 存储经过路口 $x$ 的所有公交线路及站点位置
3. 动态规划数组：
   • d[j][i]：使用不超过 $j$ 次换乘到达路口 $i$ 的最早时间
   • db[j][i][t]：使用不超过 $j$ 次换乘，在公交线路 $i$ 的第 $t$ 个站点的最早时间

算法流程

1. 初始化：

   • 读取输入数据，构建道路网络和公交线路信息
   • 初始化 DP 数组为无穷大，设置起点时间为 $t$

2. 分层动态规划：

   • 外层循环枚举换乘次数 $j$（从 $0$ 到 $k$）
   • 内层处理两种状态转移：

   转移1：在公交车上前进

   if (t)
       db[j&1][i][t] = min(db[j&1][i][t], 
                          db[j&1][i][t-1] + bus[i][t].second - bus[i][t-1].second);
   

   转移2：从路口上车

   d[j&1][x] = min(d[j&1][x], db[j&1][i][t]);
   

   转移3：换乘到其他公交车

   • 计算在路口 $i$ 换乘到公交 $x$ 的时间：
     • 如果公交车已经到达：直接上车
     • 否则：等待下一班车

3. 答案提取：

   • 在每层结束时检查是否到达终点 $n$
   • 最终输出最早到达时间或 "NIE"

时间复杂度分析

• 道路处理：$O(m)$
• 公交线路处理：$O(\sum \ell)$
• 动态规划：$O(k \times (\sum \ell + n + s))$
• 总体：在数据范围内可接受

算法标签

主要标签：

• 动态规划（Dynamic Programming）
• 分层图最短路（Layered Graph Shortest Path）
• 公交网络优化（Transit Network Optimization）

次要标签：

• 状态压缩（使用滚动数组优化空间）
• 时间离散化（处理周期性发车时间）
• 图论（Graph Theory）

代码亮点

1. 空间优化：使用 j & 1 实现滚动数组，将空间复杂度从 $O(kn)$ 降到 $O(n)$
2. 高效存储：使用哈希表存储边权，obus 数组快速查询经过某路口的所有公交
3. 时间计算：正确处理周期性发车的等待时间计算

总结

这道题通过将问题转化为分层图上的动态规划，巧妙地处理了公交网络的复杂时间约束。算法在保证正确性的同时，通过多种优化手段控制了复杂度，是一个典型的运输网络优化问题解决方案。