题目重点：城市油价不同、道路耗油不同，求 A→B 最少买油费用；用 (城市,已见最低油价) 做 Dijkstra，并检验样例 27。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 城市编号 1..n，道路耗油非负、油价非负；无限油箱且无起始免费燃料。
- 可以在沿途已访问的最便宜城市买足够多油，未来路径由离线算法选择；没有库存、携带重量或单次购油上限。
- 没有显式 n/m 上界；把不同油价数 P 作为状态规模参数。
- 道路可重复走，非负费用确保 Dijkstra 有效；不可达返回 -1。
解题路线
- 普通最短路只记城市会丢掉历史最低油价：同城虽已花更多钱，但带着更低的可购油价历史，后续长路可能更省。
- 把状态写成 (u,p)，p 是从 A 到当前城市路线上见过的最低油价。沿耗油 w 的道路到 v 时新增成本 w×p，下一状态的价格为 min(p,price[v])。
- 用最小堆 Dijkstra。每次弹出当前最低累计费用的状态；第一次弹出终点状态即全局最优。价格 p 只可能是输入城市价，最多 P 种。
- 正确性理由：对于固定路线，每段燃料可在此段之前见过的最低价城市预先购买，无限油箱使费用等于每段 w×沿途最低价；状态图准确编码该费用，边权非负。
手动走一遍
题目 5 城图中，走 3→5→1→4→2。到达 4 前经过的最低单价为 3，前三段各耗 1，总花 9；在 4 以单价 2 买 9 单位，末段花 18，总计 27。直接 3→4 耗 5 等路径并不更优。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappop, heappush
def min_fuel_cost(
city_count: int,
roads: list[tuple[int, int, int]],
prices: list[int],
start: int,
finish: int,
) -> int:
"""1-based city IDs; unlimited fuel storage and nonnegative road fuel."""
if city_count < 1 or len(prices) != city_count or not 1 <= start <= city_count or not 1 <= finish <= city_count:
raise ValueError("invalid graph")
if any(price < 0 for price in prices):
raise ValueError("negative fuel price")
graph = [[] for _ in range(city_count + 1)]
for u, v, fuel in roads:
if not 1 <= u <= city_count or not 1 <= v <= city_count or fuel < 0:
raise ValueError("invalid road")
graph[u].append((v, fuel))
graph[v].append((u, fuel))
price_values = sorted(set(prices))
index = {price: i for i, price in enumerate(price_values)}
start_state = (start, index[prices[start - 1]])
best = {start_state: 0}
heap = [(0, *start_state)]
while heap:
cost, city, cheapest_index = heappop(heap)
if cost != best[(city, cheapest_index)]:
continue
if city == finish:
return cost
cheapest = price_values[cheapest_index]
for neighbor, fuel in graph[city]:
next_index = min(cheapest_index, index[prices[neighbor - 1]])
next_state = (neighbor, next_index)
next_cost = cost + fuel * cheapest
if next_cost < best.get(next_state, float("inf")):
best[next_state] = next_cost
heappush(heap, (next_cost, *next_state))
return -1
if __name__ == "__main__":
sample = [(4, 1, 1), (5, 3, 1), (5, 4, 8), (1, 5, 1),
(3, 1, 3), (4, 2, 9), (4, 3, 5)]
assert min_fuel_cost(5, sample, [9, 11, 3, 2, 10], 3, 2) == 27
复杂度
状态至多 nP，状态边至多 2mP；优先队列时间 O(mP log(nP))，内存 O(nP+m)。当每城价格都不同，P 可达 n；若 n/m 很大，需利用价格支配关系或更紧约束进一步优化。输入没有给规模，不能保证该通用方案在某个隐藏上限内一定通过。
易错点与追问
容易失分的边界
- 只按城市维度做 Dijkstra，忽略沿途最低价格这个影响未来成本的状态。
- 按目标城市价格给刚走完的道路付费；到达后才知道新价格，不能倒买之前已耗的油。
- 把所有道路统一用起点油价，错过中途低价补油。
- 若油箱有限，最低价历史不再足够，必须把当前油量纳入状态。
- 题目例子有拼写和表达瑕疵，不能据此改变道路权重或油价数组。
继续深挖
- 若油箱容量为 C，如何把油量纳入状态并处理整数/连续油量？
- 不同价格很多时，能否对同一城市的 (花费,最低价) 做 Pareto 支配剪枝？
- 若道路耗油为 0 或油价为 0，Dijkstra 哪些性质仍成立？
- 如果要返回买油计划，如何从 predecessor 状态重建路线并安排采购？
