我在使用发现，不超过规定的成本最快的路径问题。 有类似的问题，这一个，但有它们之间有很大的区别。 在这里，可以出现在数据中的唯一记录是那些，从一个较低的点，导致一个较高的点（例如，1 - > 3可能出现，但3 - > 1可能不）（见下文）。如果不知道，我会使用Dijkstra算法。这更多的信息，可能会让它在时间比Dijkstras算法做得更快。 你觉得呢？

I'm having a problem with finding fastest path that do not exceed specified cost. There's similar question to this one, however there's a big difference between them. Here, the only records that can appear in the data are the ones, that lead from a lower point to a higher point (eg. 1 -> 3 might appear but 3 -> 1 might not) (see below). Without knowing that, I'd use Dijkstra. That additional information, might let it do in a time faster than Dijkstras algorithm. What do you think about it?

比方说，我已经有了规定的最大成本，以及4条记录。

Let's say I've got specified maximum cost, and 4 records.

// specified cost
    10 
// end point
    5
//(start point) (finish point) (time) (cost)
    2 5 50 5
    3 5 20 9
    1 2 30 5
    1 3 30 7
// all the records lead from a lower to a higher point no.

我必须决定，是否有可能从点得到（1）至（5）（它不可能孤单的时候，成本和LT没有路，不等于我们已经有了或者孤单的时候1-5之间没有连接）和如果是这样，这将是在那里得到的最快方法。

I have to decide, whether It's possible to get from point (1) to (5) (its impossible when theres no path that costs <= than we've got or when theres no connection between 1-5) and if so, what would be the fastest way to get in there.

对于这样的数据将输出：

The output for such data would be:

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

请记住，如果有一个记录，指出可以移动的 1> 2

Keep in mind, that if there's a record saying you can move 1->2

1 2 30 5

它不使您可以移动 2'。-1

推荐答案

对于每个节点的深度为n，路径到它的最低成本为 N / 2 *（最小的首先在道路边+最小边连接到节点） - 等差数列的求和。如果该计算超过所需的最大，无需检查后面的节点。切断这些节点关闭，应用Dijkstra算法就休息了。

For each node at depth n, the minimum cost of path to it is n/2 * (minimal first edge at the path + minimal edge connecting to the node) - sum of arithmetic series. If this computation exceeds the required maximum, no need to check the nodes that follow. Cut these nodes off and apply Dijkstra on the rest.