今回の問題はDijkstra法を用いて解くことができます。

(燃料を補給した回数, 最後に補給してから消費した燃料)の組を考えます。 この時、各頂点について、この組が辞書順最小になるように移動する経路が最適になります。

次のような冪等半環 \((\mathbb{N}^2, \oplus, \otimes, \bar{0}, \bar{1})\) を定めます。

• \((D_1, F_1) \oplus (D_2, F_2) = \begin{cases} (D_1, F_1) & D_1 < D_2 \lor (D_1 = D_2 \land F_1 < F_2) \\ (D_2, F_2) & \text{otherwise} \end{cases}\)
• \((D_1, F_1) \otimes (D_2, F_2) = \begin{cases} (D_1 + D_2, F_1 + F_2) & F_1 + F_2 \leq L \\ (D_1 + D_2 + 1, F_2) & \text{otherwise} \end{cases}\)
• \(\bar{0} = (\infty, \infty)\)
• \(\bar{1} = (0, 0)\)

ここで、 \(\oplus\) は辞書順最小の値を返す \(\min\) 関数であり、 \(\otimes\) は順に移動するときの燃料の消費に対応しています。

各辺について \(C\) が \(L\) 以下であれば \((0, C)\) の重みを割り当てることにすると、今回の問題は上で定義した冪等半環上における最短距離問題に等しいです。

Dijkstra法は重み付きグラフと冪等半環が与えられた時、単一始点から全頂点への最短距離を\(O(N^2)\) で求めることができるので、各頂点について予めDijkstra法を適用することで \(O(N^3+Q)\) で解くことができます。

実装例