Synchronous Shopping HackerRank

Question

我在HackerRank上试过这个Synchronous Shopping问题，我不知道如何处理它。所以我看了一下社论，我很困惑。也许我误解了Dijkstra的单源最短路径算法的工作原理。

这是从editorial采取：

他说

的状态D(V, B)的最短距离是指最短的时间需要 从买来的面膜B参观购物中心V鱼。

然后他介绍了我们可能从一个状态移动到另一个两种可能的方式，之后，他说

当计算所有的最小时间....

我认为他的意思是，在我们到达节点N后，我们应该考虑所有可能的方法来获取鱼类。所有2^k种方式。就像，我们认为

1）我们只有第一条鱼，当我们到达节点N

2）我们只有第二鱼...

3）我们只有第一鱼，第二鱼..

等。

但如果我们运行Dijkstra算法，它会计算从节点1到节点N的最短路径，但我们必须前往一个特定的路径从节点1到节点N 。我们只会沿着这些节点获得可用的鱼。我们如何计算所有其他状态？ （用不同组的鱼达到节点N）

Answer 1

让我试着帮助你，就像我最近做的那样。我将尝试一步一步地构建解决方案或主要想法。

问题概要：有两只猫，它们从购物1开始，直到N.在每次购物时，他们都购买一套鱼，如果两只猫都购买了所有的鱼，它们只能停在N。两只猫都可以走不同的路，重新逛逛购物中心。

该问题的目的是找到购买所有鱼类的最短时间，这是两只猫达到N之间的最长时间，并且两者一起购买了所有可用的鱼类。

现在，让我们尝试构建解决方案：想象一下，你没有鱼类，你只想知道猫从购物1到N的最短时间.Dijkstra可以解决这个问题，对吧？它会计算从源（商店1）到所有其他节点的所有最短时间。

下一步是添加鱼类：现在，假设我们只有一只猫，我们必须在每个站点购买鱼类。尝试想象下面的情况：图形的每个顶点只是购物中心，而不是购物，以及猫到目前为止购买的鱼的组合，存储信息。

这意味着购物可以多次添加到优先级队列，这在“正常”Dijkstra算法中不会发生。这可以让你计算从源头和所有可能的组合的最短时间，以购买鱼类购物。不幸的是，这将顶点的数量增加到O（N * 2 ^（k-1））。确保存储所有顶点的最短时间，我们将在下一步中使用它。

另一个重要的技巧是保持鱼的位置而不是列表或向量，因为购买鱼是OR操作。大多数按位操作使用的是常量O（1）。

最后一步是添加第二只猫：如果您计算如下所述的Dijkstra，您将获得所有顶点的所有最短时间，这是所有购买和购买鱼类的状态。我们只对我们在N店的情况感兴趣，而猫1和2购买的鱼的组合等于所有购买的鱼。

我们考虑到的是，如果一只猫到达N，它必须等待另一只猫到达，这意味着不管一只猫买的鱼是什么，如果其他猫到达的话，那就是精细。

从技术上讲，您将处理购物N的所有可能场景，并且如果猫1和2的鱼组合等于所购买的所有鱼，则可获得最短时间（所有可能性中最小）。 这不幸是一个详尽的方法，但通过罚款。这是Dijkstra处理后的两个堆叠。