algorithm - SPOJ FISHER 的想法

Question

我正在尝试在 SPOJ 上解决这个问题:

                  http://www.spoj.pl/problems/FISHER/

我想不出解决这个问题的办法。我在 topcoder 上发现了一些线程，但我只能推断将使用 DP。如果有人可以指导我，那将非常有帮助。

Answer 1

如果您使用动态规划来解决正常的最短路径问题，您会得到 http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm .当然，这忽略了时间限制。您始终可以通过扩展状态空间来使动态规划算法更加灵活——但要付出一定的代价。在这种情况下，不是在每个节点跟踪到目前为止找到的该节点的最便宜路径的成本，而是可以跟踪，因为 i = 1,2,3,4.. 最便宜路径的成本到节点的时间到最多 i 的那个节点。您应该能够使用用于计算单一成本的递归变体来更新此成本数组 - 每个边缘松弛都采用给定时间的最便宜成本向量，并考虑在每个偏移处添加该边缘的时间和成本以查看是否由此产生的扩展路径优于迄今为止以该边结尾的最著名路径。

我想知道你是否可以通过类似的方式转换 Dijkstra 的算法来节省时间？至少您可以先运行 Dijkstra 算法一段时间，然后丢弃所有节点的最短时间路径超过您的时间限制。