我在解决谷歌的foobar挑战时遇到了一些麻烦，我在4级，我不知道我们是怎么得到路径矩阵的

Question

我不希望任何code.Just解释我的问题(，特别是路径矩阵)，.Here是一个问题：

你和你获救的兔子囚犯需要从太空站坍塌的死亡陷阱中逃出来--而且要快！不幸的是，有些兔子被长期监禁削弱了，不能跑得很快。他们的朋友们正在努力帮助他们，但是如果你也参与进来的话，这次逃跑会快得多。防御性舱门已经开始关闭，如果你不能及时通过，你就会被困住！你需要抓住尽可能多的兔子，并通过舱壁关闭之前。

从你的起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式提供给你。每一排都会告诉你开始的时间，第一只兔子，第二只兔子，.，最后一只兔子，以及按顺序排列的舱壁。行的顺序遵循相同的模式(开始，每个兔子，舱壁)。兔子可以跳到你的怀里，所以捡起来是瞬间的，到达舱壁的同时，它的封口仍然允许一个成功的，如果戏剧性，逃跑。(别担心，任何你不接的兔子都能和你一起逃走，因为它们不再需要携带你捡到的兔子了。)如果你愿意的话，你可以重新参观不同的地方，搬到舱壁上并不意味着你必须马上离开--如果时间允许，你可以从舱壁上搬来搬去接更多的兔子。

除了花时间在兔子之间旅行外，一些路径还会与空间站的安全检查点交互，并给时钟增加时间。在时钟上增加时间会延迟舱门的关闭，如果时间恢复到0，或者在门已经关闭后有一个正数，就会触发舱壁重新打开。因此，可以在一个圆圈中行走并保持时间:也就是说，每次遍历一条路径时，都会使用或增加相同的时间。

写一个函数的形式回答(时间，time_limit)，以计算你可以捡到最多的兔子和他们是兔子，同时仍然逃避通过舱壁之前，门永远关闭。如果有多组大小相同的兔子，则按排序顺序返回具有最低囚犯in (作为索引)的兔子集。兔子被表示为一个按囚犯ID排序的列表，第一个兔子是0。最多有5只兔子，而time_limit是一个最多为999的非负整数。

例如，在以下情况下

[
  [0, 2, 2, 2, -1],  # 0 = Start
  [9, 0, 2, 2, -1],  # 1 = Bunny 0
  [9, 3, 0, 2, -1],  # 2 = Bunny 1
  [9, 3, 2, 0, -1],  # 3 = Bunny 2
  [9, 3, 2, 2,  0],  # 4 = Bulkhead
]

在时间限制为1的情况下，五个内部数组行分别指定起始点、兔子0、兔子1、兔子2和舱门出口。你可以走这条路：

Start End Delta Time Status
    -   0     -    1 Bulkhead initially open
    0   4    -1    2
    4   2     2    0
    2   4    -1    1
    4   3     2   -1 Bulkhead closes
    3   4    -1    0 Bulkhead reopens; you and the bunnies exit

有了这个解决方案，你会得到兔子1号和2号。这是这个空间站走廊的最佳组合，所以答案是1，2。

Answer 1

让我们用图论来模拟这个问题。每个兴趣点的位置(开始，每个兔子，舱壁)可以被认为是一个顶点。从每个点到另一个点的直接路径将是图中的加权边。

正如你所看到的，这里有一个稠密的图，因为有一条直接连接任意两个兴趣点的路径。

矩阵只是告诉你相对于舱壁关闭的时间成本(如果一条路径在关闭舱壁之前增加的时间比它行走所需的实际时间要多的话，它可以有一个负的权重)。这意味着它是邻接矩阵建模我们前面定义的图。

因此，矩阵的每一行表示从一个点到另一个点的路径：

• 第一行始终是起点。它告诉您从起点到任何其他点(兔子、舱壁)对关闭时间的影响。
• 然后是兔子的行，示例中的第二行告诉您从兔子#0的位置到任何其他点的时间影响等等。
• 最后，您有了从舱壁到其他点的路径。

一些解决问题的提示：

• 如果图中有负循环，你可以和所有兔子一起逃跑，因为你只需要返回一组获救的兔子.一旦检测到负循环，您就可以退出！
• 如果没有，那么你最好想想Bellman，看看这会给你带来什么(好在Bellman算法也可以用来检测负循环！)

编辑:探索矩阵背后的逻辑

为了了解它是如何工作的，让我们展开给定的示例：

time_limit = 1
times = [
    [0, 2, 2, 2, -1],  # 0 = Start
    [9, 0, 2, 2, -1],  # 1 = Bunny 0
    [9, 3, 0, 2, -1],  # 2 = Bunny 1
    [9, 3, 2, 0, -1],  # 3 = Bunny 2
    [9, 3, 2, 2,  0],  # 4 = Bulkhead
]

三角洲只是来自相关的矩阵系数。每次使用给定的delta行走路径时，都必须相应地更新time_limit：

delta = times[starting_point][ending_point]
time_limit = time_limit - delta

如果time_limit变成严格的负，舱壁关闭。如果它恢复到零(通过负路径)，它就会重新打开。这个问题要求你找到拯救大多数兔子的道路，并和它们一起逃跑。这意味着这样的路径必须以time_limit >= 0的舱壁结束。

让我们来看看这个示例，并显式地显示三角洲和time_limit更新。最好的方案是遵循以下路径(三角洲只是来自矩阵系数)：

• 启动->舱壁:成本是time[0][4] # == -1所以time_limit = 1 - (-1) = 2
• 舱壁->兔子#1:成本是time[4][2] # == 2所以time_limit = 2 - 2 = 0
• 兔子#1 ->舱壁:成本是time[2][4] # == -1所以time_limit = 0 - (-1) = 1 (兔子#1逃脱)
• 舱壁->兔子#2:成本是time[4][3] # == 2所以time_limit = 1 - 2 = -1 (舱壁关闭因为time_limit变成负值)
• 兔子#2 ->舱壁:成本是time[3][4] # == -1所以time_limit = -1 - (-1) = 0 (舱壁重新打开，你和兔子2一起逃跑)

因此，获救兔子的集合是[1, 2] (兔子#1和兔子#2 ID，按照问题描述的要求按升序排序)。