algorithm - 加权图中的最小惩罚路径

Question

考虑一个包含 N 个节点和 M 个边的无向图。每条边 M_i 都有一个与其关联的整数成本 C_i。

路径的惩罚是一对节点A和B之间路径中每个边成本的按位或。换句话说，如果路径包含边 M₁,M₂,..., M_k 则该路径的惩罚为 C₁ 或 C₂ 或 ... 或 C_k。

给定一个图和两个节点，A和B，找到A和B之间的路径可能的最低处罚并打印其处罚；如果不存在这样的路径，则打印 −1 表示不存在从 A 到 B 的路径。

注意:允许循环和多条边。

约束:

1≤N≤10³

1≤M≤10³

1≤C_i<1024

1≤U_i，V_i≤N

1≤A，B≤N

A≠B

这个问题是在一场比赛中提出的，它已经结束了，我浏览了教程，但无法得到它。谁能解释或给出如何继续的答案？

Answer 1

可以使用动态规划通过以下递归公式来解决:

D(s,0) = true
D(v,i) = false OR D(v,i) OR { D(u,j) | (u,v) is an edge, j or c(u,v) = i }

其中s是源节点。

这个想法是D(v,i) == true当且仅当存在从s到v的带有权重的路径正好是i。
现在，您在动态规划中迭代修改图形，直到它收敛(最多在 n 次迭代之后)。
这基本上是 Bellman-Ford algorithm 的变体。 完成为解决方案创建 DP 表后，最小路径为 min { x | D(t,x) = true}(其中 t 是目标节点)。

时间复杂度为O(m*n*log_2(R))，其中R是允许的最大权重(在您的情况下为1024)。