Problem Description

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<0$, then the vehicle cannot traverse this edge.

Some nodes on the map are charging stations. Xiaoming may pass through multiple charging stations, but because charging takes time to find a charger, he decides that during the trip he will charge at most at one charging station. The price to charge one unit is one dollar. Xiaoming's goal is to reach the destination with the minimum cost.

For example, consider the following three graphs. We use square nodes to represent charging stations, and circular nodes to represent nodes where charging is not available. Suppose the battery capacity $B=100$, the start is $s$, the destination is $t$, and the initial battery level is $20$.

In the figure below, the vehicle can reach $t$ from $s$, and the minimum charging cost is $0$.

:::align{center} :::

In the figure below, the vehicle cannot reach $t$ from $s$.

:::align{center} :::

In the figure below, the vehicle can reach $t$ from $s$, and the minimum charging cost is $35$.

:::align{center} :::

Input Format

$$\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.

Output Format

$$a$$

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

6 5 1 6
100 20
1 2 -5
2 3 10
3 4 -25
4 5 5
5 6 -5
1 4

0

7 7 1 7
100 20
1 2 -15
2 3 200
3 4 -60
3 5 -80
4 6 -70
5 6 -40
6 7 20
1 6

-1

7 7 1 7
100 20
1 2 -10
2 3 -5
3 4 -20
3 5 -30
4 6 -40
5 6 -10
6 7 20
1 3

35

7 7 1 7
100 60
1 2 -10
2 3 -5
3 4 -20
3 5 -30
4 6 -40
5 6 -10
6 7 -5
0

0

Hint

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