P15238 [NHSPC 2025] Electric Vehicle Charging Planning Problem

Xiaoming bought an electric vehicle, whose battery capacity is $B$. Xiaoming knows the initial battery level $b$. He wants to plan a route from the start to the destination so that the required charging cost is as small as possible. On some road segments the vehicle consumes power (such as flat roads or uphill), and on some road segments it gains power (such as downhill). **Power gained on these charging segments is free of charge**. We use a directed graph to represent the map. The weight of an edge represents how the battery level changes after driving through that edge: if the vehicle gains power, the edge weight is a positive number; otherwise, if the vehicle consumes power, the edge weight is a negative number. We assume the graph has no positive cycles. While driving, the battery level must always be greater than or equal to $0$, and no matter how much power is gained, the battery level is at most $B$. More precisely, let $p$ be the current battery level, and consider an edge with weight $w$: - If $w$ is non-negative, then the vehicle can always traverse this edge (even if $p=0$), and the remaining battery level becomes $\min(B, p+w)$. - If $w$ is negative and $p+w \ge 0$, then the vehicle can traverse this edge, and the remaining battery level after traversing it becomes $p+w$. - However, if $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$ is the number of nodes. - $m$ is the number of edges. - $s$ is the index of the start node. - $t$ is the index of the destination node. - $B$ is the battery capacity. - $b$ is the initial battery level. - $u_i, v_i, w_i$ mean that the graph has an edge from node $u_i$ to node $v_i$ with weight $w_i$. - $g$ is the number of charging stations. - $p_i$ is the node index of the $i$-th charging station.

$$a$$ - $a$ is the minimum required charging cost. If there is no path to reach the destination, then $a = -1$.

### Constraints * $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$, and $u_i \neq v_i$. * $-10^9 \le w_i\le 10^9$. * $0 \le g\le n$. * $1 \le p_i \le n$. * It is guaranteed that the graph has no positive cycles. * All input values are integers. ### Scoring This problem has four subtasks, with the additional constraints shown below. Each subtask may contain one or more testdata files. You will receive the score for a subtask only if you pass all testdata files in that subtask. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 15 | The input satisfies that all road segments never charge, i.e. $w_i\le 0$, and there are no charging stations, i.e. $g = 0$. | | 2 | 30 | The input satisfies that all road segments never charge, i.e. $w_i\le 0$. | | 3 | 23 | The input satisfies that there are no charging stations, i.e. $g = 0$. | | 4 | 32 | No additional constraints. | Translated by ChatGPT 5