题解：P15238 [NHSPC 2025] 电动车充电规划问题
前言
题目传送门
思路讲解
首先我们需要判断做这道题的算法是什么。
这题的边权 \(w_i\) 有正有负，而 Dijkstra 只能做全正或全负，全负的时候还不能有环，所以不行。
这题 \(n\le10^3\)，而 Floyd 的时间复杂度是 \(O(n^3)\)，很明显会超时。
这样的话，我们就要用 SPFA 做了。
Subtask 1
没有充电站和充电边，直接求出最短路的耗油量，和初始油量作比较，如果耗油量 \(\le\) 初始油量，输出 \(0\)，否则输出 \(-1\)。
Subtask 2
木有充电路，可以先用上面的方法做，如果可以走到终点就直接输出 \(0\)，如果不行就枚举经过每个加油站可不可以到达终点，对于一个加油站 \(u\)，定义 \(d(u)\) 为起点到 \(u\) 最少耗油量，\(e(u)\) 为最低初始油量，如果可以达到终点，输出 \(e(u)-(b-d(u))\)。
Subtask 3
我们可以增加一个起点 \(s'\) 和边 \((s',s)\)，权值（即权重）为 \(B-b\)，将耗电设为正，充电站设为负。用 Bellman-Ford 算出 \(d(u)\)。在松弛时考虑边 \((u,v)\) 且权值为 \(w\) 的边。
若 \(d(t)=\infty\)，代表无法抵达，输出 \(-1\)，否则输出 \(0\)。
Subtask 4
我们发现 Subtask 3 可以处理没有充电站，Subtask 2 可以处理没有充电边，所以我们可以把两种做法合并，在 Subtask 3 的基础上加上 Subtask 2 的做法。