题目大意

给定一个无向图，每条边有颜色 $C_i$ 和改色花费 $P_i$。机器人从节点 $1$ 出发，每次你指定一个颜色，如果从当前节点出发恰好只有一条边是该颜色，机器人就会走那条边，否则停止。可以通过花费 $P_i$ 改变边的颜色。求从节点 $1$ 到节点 $N$ 的最小总花费，若无法到达输出 $-1$。

解题思路

核心观察

在节点 $u$，如果我们想用颜色 $c$ 作为指令，那么 $u$ 的所有出边中颜色为 $c$ 的边必须恰好只有一条。

对于某条边 $e$，如果我们想把它作为颜色 $c$ 的唯一出边：

• 如果 $e$ 原本颜色不是 $c$，需要花费 $P_e$ 改色
• $u$ 的其他颜色为 $c$ 的出边都必须改色（总花费为这些边的 $P_i$ 之和）

建图技巧

直接枚举所有 $(节点, 颜色)$ 状态会超时，需要优化：

1. 对每个节点的出边按颜色分组
2. 虚拟节点技术：
   • 对于节点 $u$ 的每种颜色 $c$，如果该颜色有 $k$ 条边，就创建一个虚拟节点
   • 从 $u$ 连接到虚拟节点，边权为 $0$
   • 从虚拟节点连接到每条颜色为 $c$ 的边的终点，边权为 总花费 - 该边花费
   • 这样选择任意一条颜色为 $c$ 的边时，代价就是 总花费 - 该边花费 + 该边改色花费

算法流程

1. 读入图数据，建立初始邻接表
2. 对每个节点 $u$：
   • 统计每种颜色的总花费和边数
   • 如果某种颜色只有一条边，直接使用该边（可能花费 $0$ 或 $P_e$）
   • 如果某种颜色有多条边，创建虚拟节点并连接
3. 在扩展图上跑 Dijkstra 最短路
4. 输出 $dis[N]$ 或 $-1$

复杂度分析

• 时间复杂度：$O((N+M)\log(N+M))$，其中虚拟节点最多 $M$ 个
• 空间复杂度：$O(N+M)$

总结

本题的关键在于将颜色约束转化为图论问题，通过虚拟节点技术避免状态爆炸，最终用最短路算法求解。