解题思路
油箱容量只有 B≤100,把「当前驿站 + 剩余电量」看成一层状态,在这张状态图上跑 Dijkstra。
- 状态 (u,f) 表示在 u 号驿站、电池还剩 f 格。出发是 (1,B),耗时 0。
- 转移有两类:在当地充
1 格,到 (u,f+1),加时 su(要求 f<B);或走一条耗能 a、耗时 w 的路,到 (v,f−a),要求 f≥a。
- 边是双向的。第一次弹出 C 号驿站的某个状态,就是最短时间。
- 若所有 (C,f) 都到不了,答案为
-1。耗能为 0 的充电(su=0)只会把电量一格格加满,状态数有限,不会死循环。