颜色与路径

设 $f(P,c)$ 为路线 $P$ 中颜色不为 $c$ 的经过次数。费用为 $\min_c f(P,c)$，所以答案为 $\min_P\min_c f(P,c)=\min_c\min_P f(P,c)$。固定颜色 $c$，将这种颜色的边权设为 0，其余边权设为 1，用 0-1 BFS 求最短路，再对所有颜色取最小值。 零权松弛入双端队列队首，单位权松弛入队尾；同时存储入队时的距离，跳过过期项。时间 $O(K(V+E))$，空间 $O(V+E)$。由于边权非负，删去环不会增加固定颜色的费用。因此子任务 1 可用 DFS 枚举所有简单路径并统计颜色，宽松上界为 $O(E!K)$，$E\leq8$ 时足够。答案及有限最短距离均在 0 到 $V-1$ 之间，有符号64位整数足够。

Solution written by GPT6.1