AtCoder E题：汽车旅行最小加油次数解法及Floyd-Warshall逻辑疑问

1. 最初方法的问题 #

你用Floyd-Warshall重构最短路径的思路错误在于：最短路径不一定是可行路径。题目要求每次行驶必须在满油状态下能完成路段（即路段长度≤L），但最短路径可能包含某一段子路径的长度超过L，导致这段路根本开不过去——哪怕整体路径长度最短，也不具备实际通行的可能。

2. 官方题解逻辑的正确性解释 #

官方题解的核心是把问题转化为“满油行驶段数”的计算，而非直接计算加油次数，这是你产生疑问的关键：

关键定义 #

• dist[i][j]：用Floyd求出的i到j的最短路径长度，确保我们只考虑最紧凑的通行可能性。
• ok[i][j]：当dist[i][j] ≤ L时为真，表示从i满油出发可以直接开到j（中间无需加油）。
• dp[i][j]：表示从i到j需要经过的满油行驶段数，初始规则：
  • 若ok[i][j]为真，dp[i][j] = 1（对应1段满油行驶，无需额外加油）；
  • 若i==j，dp[i][j] = 0；
  • 其余情况设为无穷大。

为什么ok[i][k]和ok[k][j]均为1时，dp[i][j]是2？ #

ok[i][k]仅保证“i满油能到k”，ok[k][j]仅保证“k满油能到j”，但不代表i满油到k后剩余的油量足够开到j。举个例子：

• L=5，dist[i][k]=4，dist[k][j]=3：此时ok[i][k]和ok[k][j]都为真，但i满油到k后只剩1单位油，远不够开3到j，必须在k加油才能继续行驶。

这种情况下，i→k是1段满油行驶，k→j是另1段满油行驶，总共2段，对应加油次数为段数-1=1次（出发时的满油不算加油）。而Floyd-Warshall转移时dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])得到的2，正好是正确的段数，最终答案只需减1即可得到加油次数。

逻辑合理性 #

这种转化的优势在于：无需跟踪剩余油量，只需通过“满油段数”的最小化来等价于加油次数的最小化——每多一段满油行驶，就意味着需要多一次加油（除了出发时的第一段）。Floyd-Warshall的转移逻辑正好能找到从i到j的最少满油段数，从而得到最少加油次数。

内容的提问来源于stack exchange，提问作者Szyszka947