我在比赛中的某个地方发现了这个问题，但尚未提出解决方案。我正在考虑应用Dijkstra的东西，但不是很清楚:
``您会得到一张加权的城市连通图，所有边缘的权重都为正。一些城市(节点)有加油泵，而有些则没有。您有一辆油箱容量为C的自行车。也就是说，满油箱时，汽车可以行驶C距离单位。在任何有加油泵的城市，汽车都可以将油箱加满。找出给定源与给定目的地之间的最短路径。假设你从一个满满的坦克开始。''
我有一个O(mn logn)会被它接受的感觉。
最佳答案
基本上，您需要在自行车到达时根据剩余燃料将每个节点n_i拆分为多个节点，我们称它为(n_i，r)。您无需一开始就创建所有(n_i，r)，就可以快速创建它。
然后类似于Dijkstra，从节点(n_0，C)开始，每次找到下一个(n_x，r)，您都可以以最小的距离到达。并更新连接到(n_x，r)的所有节点(n_y，ry)。如果n_y有泵，则ry会重置为C。如果对于n_y，已经有一个节点(n_y，r)并且r> = ry，那么您无需创建新的节点(n_y，ry)，只需忽略它即可。
我不能说运行时的复杂性，但是它足以在竞赛中获得AC。