P15238 [NHSPC 2025] 电动车充电规划问题

小明买了一台电动车，其电池容量为 $ B $ 。小明知道电动车的初始电量 $ b $ ，他要规划从起点开到终点的路线，使得所需的充电费用越少越好。电动车在一些路段会耗电（如平路或是上坡），在一些路段会充电（如下坡）。**这些充电路段是不会收费的**。我们用一个有向图表示地图，边的权重代表电动车开过此边会让电量增加或减少，如果开过此边会充电，则边的权重为一个正数，反之如果开过此边会耗电，则边的权重为一个负数。我们假设图没有正环。 电动车在行驶时，电量需要永远大于等于 $ 0 $ ，而且无论充电量多大，电量最多为 $ B $ 。更明确地说，令 $ p $ 为电动车目前电量，并考虑一个权重为 $ w $ 的边：如果 $ w $ 非负数，则电动车一定可以开过此边（即使电量 $ p=0 $ ），且剩余电量为 $ \min(B, p+w) $ ；如果 $ w $ 是负数，且 $ p+w \ge 0 $ ，则电动车可以开过此边，且开过此边后的剩余电量为 $ p+w $ ；然而，如果 $ p+w

$$ \begin{aligned} &n \; m \; s \; t \\ &B \; b \\ &u_1 \; v_1 \; w_1 \\ &u_2 \; v_2 \; w_2 \\ &\vdots \\ &u_m \; v_m \; w_m \\ &g \; p_1 \; p_2 \; \cdots \; p_g \end{aligned} $$ - $n$ 为节点数。 - $m$ 为边数。 - $s$ 为起点编号。 - $t$ 为终点编号。 - $B$ 为电池容量。 - $b$ 为电池初始电量。 - $u_i, v_i, w_i$ 代表图中有一个边由节点 $u_i$ 至节点 $v_i$，且权重为 $w_i$。 - $g$ 为充电站个数。 - $p_i$ 为第 $i$ 个充电站的节点编号。

$$a$$ - $a$ 代表最少所需的充电费用。如果不存在路径抵达终点，则 $a = -1$。

### 数据限制 * $1 \le n\le 10^3$。 * $1 \le m\le 10^4$。 * $1 \le s,t\le n$。 * $1 \le B\le 10^9$。 * $0 \le b\le B$。 * $1 \le u_i, v_i\le n$，且 $u_i \neq v_i$。 * $-10^9 \le w_i\le 10^9$。 * $0 \le g\le n$。 * $1 \le p_i \le n$。 * 保证图没有正环。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 15 | 输入满足所有路段都不会充电，即 $w_i\le 0$， 且没有充电站，即 $g = 0$。 | | 2 | 30 | 输入满足所有路段都不会充电，即 $w_i\le 0$。 | | 3 | 23 | 输入满足没有充电站，即 $g = 0$。 | | 4 | 32 | 无额外限制。 |