题目概述

Bajtazar 需要从城镇 $1$ 前往城镇 $n$（拜托城），途中有 $m$ 条双向道路。每条道路有通行时间，并且可能遇到特定种类的怪物。要安全通过有怪物的道路，必须在遇到该怪物之前就获得对应的剑。剑只能在有铁匠的城镇打造，每个铁匠能打造特定种类的剑。

关键约束：在通过一条道路时，如果该道路上有怪物，必须确保当前已经拥有对抗所有这些怪物的剑。

问题分析

核心难点

1. 剑的获取顺序影响路径选择：可能需要绕路先去有铁匠的城镇获取必要的剑
2. 状态依赖：能否通过某条道路取决于当前拥有的剑的集合
3. 组合爆炸：剑的种类组合有 $2^p$ 种可能

重要观察

• 怪物种类数 $p \leq 13$，可以使用状态压缩
• 剑一旦获得就可以永久使用（可携带任意多把剑）
• 道路是双向的，且通行时间相同
• 同一个城镇可能有多个铁匠

算法思路

状态设计

定义状态：dp[u][mask] 表示到达城镇 $u$ 且当前拥有剑的状态为 mask 时的最短时间。

• u：当前所在城镇（$1 \leq u \leq n$）
• mask：二进制状态，第 $i$ 位为 1 表示拥有对抗怪物 $i$ 的剑
• 状态总数：$n \times 2^p$，在题目限制下是可接受的

预处理

1. 铁匠信息：对于每个城镇，预处理在该城镇可以获得的所有剑的集合
2. 道路信息：对于每条道路，预处理需要哪些剑才能通过（怪物集合的位掩码）

状态转移

使用 Dijkstra 算法 在状态空间中进行搜索：

1. 初始状态：dp[1][初始剑集合] = 0（开始时没有剑，初始剑集合为 0）

2. 状态扩展：

   • 移动操作：从状态 (u, mask) 尝试移动到相邻城镇 v
     • 检查：mask 是否包含道路 (u,v) 上所有怪物对应的剑
     • 如果满足条件，则更新 dp[v][mask]
   • 获取剑操作：在城镇 u 获取该城镇所有可获得的剑
     • 新状态：mask' = mask | swords[u]
     • 更新 dp[u][mask']（时间不变，只是剑集合扩大）

3. 终止条件：当第一次到达状态 (n, any_mask) 时，即为答案

算法复杂度

• 状态数：$O(n \cdot 2^p)$
• 每个状态最多扩展 $O(m)$ 次
• 总复杂度：$O(n \cdot 2^p \cdot m)$，在题目限制下可行

关键技巧

位运算优化

• 剑集合检查：检查当前剑集合 mask 是否能应对怪物集合 monster_mask：

  if ((mask & monster_mask) == monster_mask) {
      // 可以通过
  }
  

• 剑集合合并：获取新剑时使用位或运算：

  new_mask = mask | available_swords[u]
  

搜索策略

使用优先队列（最小堆）按时间排序，保证第一次到达某个状态就是最短时间，这是 Dijkstra 算法的核心思想。

特殊情况处理

1. 无法到达：如果所有状态搜索完成后仍未到达城镇 $n$，输出 -1
2. 无剑需求：如果道路没有怪物，任何剑集合都可以通过
3. 重复铁匠：同一个城镇的多个铁匠，剑集合取并集

实例分析

样例 1 解析

路径：$1 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 6$

• 在城镇 $2$ 获得对抗怪物 $2$ 的剑
• 返回 $1$ 时已有剑，可以安全通过
• 从 $1$ 到 $4$ 需要对抗怪物 $2$，已有对应剑
• 从 $4$ 到 $6$ 没有怪物，直接通过

样例 2 解析

• 道路 $(1,2)$ 需要对抗怪物 $1$ 的剑
• 剑在城镇 $2$ 获得，但要到达城镇 $2$ 必须先通过道路 $(1,2)$
• 形成死锁，无法到达

总结

本题是状态压缩最短路的经典应用，通过将剑的拥有情况编码为二进制状态，将复杂的资源约束问题转化为在扩展状态空间中的标准最短路问题。算法核心在于合理的状态设计和高效的位运算处理。

关键洞察：剑的获取是单调递增的（一旦获得就不会丢失），这使得状态转移具有良好性质，适合使用 Dijkstra 算法求解。