在图中从 1 个城市到另一个城市旅行的最低成本。 （不是 dijkstra 的算法）
Minimum cost to travel from 1 city to another in a graph. (Not dijkstra's algorithm)
Bob住在Oiland，那里有N个城市，编号从1到N，M条道路连接着这些城市。他想去 B 城市与来自他居住的城市 A 的 Alice 见面。这是一次长途旅行，Bob 将在多个加油站停下来为 hi car 加油。
不同站点的燃油价格不同，Bob 准备绕道前往价格较低的站点。 Bob 有一张地图，上面标有 N 个城市和 S 个加油站。从地图上，他知道在两个城市之间行驶需要多少升燃料，以及每个加油站每升的价格。汽车的油箱也有最大容量 C 升。写一个程序找出从 A 城市到 B 城市旅行的最低花费。他从空油箱开始，A 城市有一个加油站。
Constraints:
2 <= N cities <= 1000
1 <= M connecting roads <= 10000
1 <= S fuel stations <= 120
1 <= C fuel tank capacity <= 100000
1 <= G fuel needed to travel between any 2 cities <= 100000
我无法解决。如果有人能给出它的解决方案或告诉一些提示来解决它，那将是有帮助的。
在每个加油站，driver 不仅需要决定下一步去哪里，还需要决定购买多少燃料。
以下是一个未经检验的想法，可能行得通也可能行不通。
这个问题可以通过修改后的 smallest-weight-path 算法来解决，比如说 Dijkstra 的算法。我们需要修改重量的概念。在我们的例子中，它不是一个单一的数字，而是一个 函数 ，具体来说，是将油箱中剩余的燃料量映射到花费的金额的函数。举一个具体的例子，考虑从原点 A 到最近的泵 X 的一条边。假设距离为 100 公里，油耗为 10 升/100 公里，A 处的燃油价格为 2 美元/升，油箱可以50 升。 driver 可以购买 10 到 50l 的任何地方以从 A 到 X，因此 AX 边的权重是一个分段线性函数，定义在区间 0..40 上，在 0 处取值 $20，在40.
现在，如果 driver 从 X 继续到 Y，正常算法会将到目前为止的权重添加到边缘的权重。但是我们有两个权重函数，一个是 piecewise-linear monotonically-increasing（到目前为止的权重），另一个是 single-segment piecewise-linear（出边的权重）。我们需要通过以下方式将两者结合起来。将第一个函数左移从 X 到 Y 所需的燃料量，舍弃负数部分，加上相应的价格。对于函数图的其余部分，考虑与每个段对应的燃料价格。如果当地的燃料更贵，请保持原样；如果在当地更便宜，则重新计算该段；如果该段代表空罐，则按当地价格加满。
查看此操作的另一种可能更简单的方法是想象一个看起来像这样的列表：“此时我可能有多达 x1 升的燃料，价格为每升 p1，还有多达 x2 升价格为 p2 的燃料，以及...” 当您到达加油站时，将列表中所有比当地价格贵的项目都放下，然后加满。
现在当普通算法考虑两条通往同一个顶点的路径时，它需要决定哪个权重更好。由于权重现在是一个函数，修改后的算法需要取两个函数中的最小值，这将是另一个函数，再次 piecewise-linear.
所以你在图的每个顶点都有 monotonically-increasing piecewise-linear 函数；函数图的每个点对应于在剩余给定燃料量的情况下到达该顶点的最便宜方式。
您的最终解决方案是目标顶点中 0 处的函数值。
Bob住在Oiland，那里有N个城市，编号从1到N，M条道路连接着这些城市。他想去 B 城市与来自他居住的城市 A 的 Alice 见面。这是一次长途旅行，Bob 将在多个加油站停下来为 hi car 加油。 不同站点的燃油价格不同，Bob 准备绕道前往价格较低的站点。 Bob 有一张地图，上面标有 N 个城市和 S 个加油站。从地图上，他知道在两个城市之间行驶需要多少升燃料，以及每个加油站每升的价格。汽车的油箱也有最大容量 C 升。写一个程序找出从 A 城市到 B 城市旅行的最低花费。他从空油箱开始，A 城市有一个加油站。
Constraints:
2 <= N cities <= 1000
1 <= M connecting roads <= 10000
1 <= S fuel stations <= 120
1 <= C fuel tank capacity <= 100000
1 <= G fuel needed to travel between any 2 cities <= 100000
我无法解决。如果有人能给出它的解决方案或告诉一些提示来解决它，那将是有帮助的。
在每个加油站，driver 不仅需要决定下一步去哪里，还需要决定购买多少燃料。
以下是一个未经检验的想法，可能行得通也可能行不通。
这个问题可以通过修改后的 smallest-weight-path 算法来解决，比如说 Dijkstra 的算法。我们需要修改重量的概念。在我们的例子中，它不是一个单一的数字，而是一个 函数 ，具体来说，是将油箱中剩余的燃料量映射到花费的金额的函数。举一个具体的例子，考虑从原点 A 到最近的泵 X 的一条边。假设距离为 100 公里，油耗为 10 升/100 公里，A 处的燃油价格为 2 美元/升，油箱可以50 升。 driver 可以购买 10 到 50l 的任何地方以从 A 到 X，因此 AX 边的权重是一个分段线性函数，定义在区间 0..40 上，在 0 处取值 $20，在40.
现在，如果 driver 从 X 继续到 Y，正常算法会将到目前为止的权重添加到边缘的权重。但是我们有两个权重函数，一个是 piecewise-linear monotonically-increasing（到目前为止的权重），另一个是 single-segment piecewise-linear（出边的权重）。我们需要通过以下方式将两者结合起来。将第一个函数左移从 X 到 Y 所需的燃料量，舍弃负数部分，加上相应的价格。对于函数图的其余部分，考虑与每个段对应的燃料价格。如果当地的燃料更贵，请保持原样；如果在当地更便宜，则重新计算该段；如果该段代表空罐，则按当地价格加满。
查看此操作的另一种可能更简单的方法是想象一个看起来像这样的列表：“此时我可能有多达 x1 升的燃料，价格为每升 p1，还有多达 x2 升价格为 p2 的燃料，以及...” 当您到达加油站时，将列表中所有比当地价格贵的项目都放下，然后加满。
现在当普通算法考虑两条通往同一个顶点的路径时，它需要决定哪个权重更好。由于权重现在是一个函数，修改后的算法需要取两个函数中的最小值，这将是另一个函数，再次 piecewise-linear.
所以你在图的每个顶点都有 monotonically-increasing piecewise-linear 函数；函数图的每个点对应于在剩余给定燃料量的情况下到达该顶点的最便宜方式。
您的最终解决方案是目标顶点中 0 处的函数值。