the*_*one 5 algorithm dijkstra shortest-path graph-algorithm
我在比赛的某个地方发现了这个问题,但还没有找到解决方案.我正在考虑应用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。