c++ - 图可除性

Question

给定一个简单的无向图，其中包含编号为 1 到 N 的 N 个顶点，每个顶点包含来自 {1,2,..7} 的数字。从带有空字符串 S 的顶点 1 开始，我们通过一些顶点(没有限制)到达顶点 N。对于途中的每个顶点，我们将相应的数字添加到字符串 S 的右侧。最后我们得到S 为十进制整数。要求你找到这样一种方式满足 S 可以被它的所有数字整除，并且 S 的数字和必须尽可能小。

输入

有几个测试用例(最多十五个)，每个测试用例组成如下:

The first line contains a positive integer N (N ≤ 100).
The second line contains N digits (separated by spaces), the i-th digit is the value of the i-th vertex.
N last lines, each contains N values of {0, 1} (separated by spaces), the j-th value of the i-th line is equal to 1 if there is an edge connecting two vertices (i, j), otherwise 0.

输入以 N = 0 结束。

输出

对于每个测试用例，在一行上输出找到的最小数字总和，如果没有解决方案，则输出 -1。

例子

输入: 4

1 2 1 4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

输出: 7

请指导我

可以存在自循环和循环，使得节点 1 和节点 N 可以被访问任意次数

Answer 1

如果给定的图被转换为其他图，其中不允许循环，这个问题可以用 Dijkstra's algorithm 解决。 .

为此，让我们从字符串被 7 整除开始。看看这个序列:1, 10, 100, ... (mod 7)。因为 7 是质数，所以 10^7-1 = 1 (mod 7) 因为 Fermat's little theorem .这意味着 1, 10, 100, ... (mod 7) 序列是周期性的，周期为 6。这将用于转换图形，也允许递归计算 S_n (mod 7 ) 使用 S_n-1 (mod 7): S_n = S_n-1 + 10^n%6 * n_th_digit (mod 7).

有必要从节点 N 开始搜索最短路径，因为这条路径可能会在转换图的几个节点之一结束。这也允许快速确定(使用路径的前 2 个节点)是否允许访问节点“5”、节点“4”和其他“偶数”节点。

算法的开放集(优先级队列)应该包含优先级本身(数字总和)只要 3 个附加位和 3 个余数:允许“4”，访问“3”，访问“7”，S % 3、S % 7 和 S.length % 6。

图形应按如下方式转换。每个顶点扩展为 3 个顶点，一个仅允许 S%3==0，其他 - S%3==1 和 S%3 ==2。然后每个顶点扩展到 7(for S%7)，然后每个顶点扩展到 6(for S.length % 6)。可以将所有这些扩展拟合到原始图形:只需向每个节点添加一个 3D 数组(大小 3*7*6)的反向指针。在搜索最短路径时，非空反向指针确定算法的闭集(它们不允许循环)。当找到最短路径时，后向指针允许重建该路径中的节点序列。找到最短路径的时刻是通过使用 (node_3_not_visited || S%3==0) && (node_7_not_visited || S%7==0) 访问节点 1 来确定的。