题目重点：用最多 K+1 条边的 Bellman-Ford 分层转移限制中转次数，区分路径价格、节点访问和实时更新。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每条有向航班边票价非负，src/dst 给定，最多 K 个中间停靠城市即最多 K+1 条边；若‘stops’包括终点，边数公式必须按现场题面改。
- 同城 src=dst 时价格 0；不可达返回约定的无解值。起飞时间、航班衔接与库存未在题目出现，不纳入基础图模型。
- 允许同一城市重复访问与否不影响非负票价的最优解：正价环不会改进价格；若零价环存在，可取不重复的等价最优路径。
解题路线
- 最直接的 DP 令 prev[v] 为用至多 e−1 条边从 src 到 v 的最小价，curr 先复制 prev，再逐条航班 u→v(price) 做 curr[v]=min(curr[v],prev[u]+price)。共迭代 e=1..K+1；一定从 prev 读，不能本层原地读写，否则一次迭代可以串联多条边。
- 若要输出路径，记录每一层的 predecessor 与最优价格，并比较终点在哪一层首次达到最终最优。多个同价路径的 tie-break 另定。
- 非负价也可用状态 (city,edges_used,cost) 的优先队列，但不能只设 city visited；到同一城市的更贵但用边更少的状态可能有用。简单 DP 对 K 较小且边表静态更可靠。
- 规模大/实时价格变化时先明确查询量、更新频率与 K 上限。若更新很多而查询少，按请求跑分层 DP；若查询很多且价格较稳定，可缓存热点 src/dst/K 结果并在航线变价后失效，或使用有版本的边表。
手动走一遍
训练例 A→B 价 10、B→C 价 10、A→C 价 50。K=0 只允许一条边，答案 50；K=1 可走 A→B→C，答案 20。若第一轮对同一数组原地松弛且边顺序先 A→B 后 B→C，就会错误地在 K=0 得 20。
规模与取舍
V 个城市、E 条航班、K 次中转：价钱 DP O((K+1)E) 时间、O(V) 滚动空间；要恢复路径则 O((K+1)V) 状态空间。价格和必须防固定宽整数溢出。
易错点与追问
容易失分的边界
- 把 K 次中转写成 K 条边，少允许一段航班。
- 原地更新同一层数组，让路径偷偷超过边数上限。
- Dijkstra 只以城市做 visited，丢掉边数较少的候选。
- 把航班时刻/转机最短时间当作原题已给约束。
- 实时价格更新时返回过期缓存而不带版本。
继续深挖
- 若必须最短转机时间或有出发时刻，状态应如何扩展？
- 同价方案要优先少中转，DP tie-break 怎么设计？
- 边价会变且每秒数十万查询，怎样选择缓存与失效粒度？
