魔法森林问题文字题解

核心问题定位

本题的本质是在无向图中寻找从节点 $1$ 到节点 $N$ 的路径，使得路径中所有边的 $A_i$ 最大值与 $B_i$ 最大值之和最小。关键在于明确：所需携带的 A 型精灵数量是路径中所有边 $A_i$ 的最大值，B 型精灵数量是路径中所有边 $B_i$ 的最大值，总数量为两者之和。

解题核心思路

采用“固定一个约束，优化另一个约束”的策略，核心逻辑围绕“按 $A_i$ 排序 + 动态维护最小 $B$ 值”展开：

1. 边的排序处理：将所有边按照 $A_i$ 从小到大排序。这样做的目的是，依次加入边时，当前加入的边的 $A_i$ 就是当前路径的最大 $A$ 值（$A_{\text{max}}$），无需再考虑更小的 $A_i$ 约束。

2. 分批加入边与更新最小 $B$ 值：按排序后的顺序，分批加入 $A_i$ 相同的所有边。每加入一批边后，通过广度优先搜索（BFS）动态更新各节点的最小所需 $B$ 值——即到达该节点时，路径中 $B_i$ 的最小可能最大值。

3. 计算最优解：每完成一批边的加入和 $B$ 值更新后，检查是否能到达节点 $N$。若能到达，计算当前 $A_{\text{max}}$（当前批次边的 $A_i$）与节点 $N$ 的最小 $B$ 值之和，持续记录该和的最小值，即为最终答案。

关键逻辑说明

• 排序后分批处理边，保证了每次处理时 $A_{\text{max}}$ 是递增的，只需专注于优化 $B_{\text{max}}$，将双约束问题转化为单约束优化问题，降低求解难度。
• BFS 用于更新最小 $B$ 值时，利用了“当前可达节点通过新加入的边，能到达更多节点且可能获得更小的 $B_{\text{max}}$”的特性，确保每个节点的 $B$ 值始终是当前最优的。
• 若遍历所有边后仍无法到达节点 $N$，则输出 $-1$；否则输出记录的最小和。

算法合理性

该思路通过排序固定 $A_{\text{max}}$ 的递增趋势，再通过 BFS 高效维护每个节点的最小 $B_{\text{max}}$，既保证了覆盖所有可能的最优路径，又控制了时间复杂度，能够适配题目给出的数据范围（$N \leq 50000$，$M \leq 100000$）。