P3280 [SCOI2013] Motorcycle Trading

After being discharged from the hospital, mzry1992 bought a new motorcycle and started a gold delivery business among nearby cities. In the place where mzry1992 lives, cities are connected by bidirectional highways. In addition, each highway has a load limit: ignoring the weight of the rider and the motorcycle, if the amount of cargo carried exceeds a certain value, that highway cannot be used. This year, mzry1992 received $n$ orders from $n$ different cities. Each order either requests to buy up to a certain amount of gold from him, or to sell up to a certain amount of gold to him. Since orders do not arrive simultaneously, to maintain his reputation, mzry1992 must trade with customers in the order the orders arrive. When trading with the $i$-th customer, he performs the following steps: 1. Travel to the city of the $i$-th customer. Passing through other cities en route is fully allowed. 2. Trade with the $i$-th customer. In this process, he wants to maximize the transaction amount subject to the following two constraints: (a) After finishing the transaction with the last customer, he must hold no gold. (b) Because gold is valuable, he is not allowed to overbuy in a way that would force him to discard gold later during transportation. Initially, mzry1992 is located in the city of the first order. Here is some good news: someone has given mzry1992 a free trial to use the railway system among nearby cities. Specifically, if he wants to travel from city $A$ to city $B$, and both $A$ and $B$ have railway stations, then he can carry both gold and his motorcycle by train from $A$ to $B$, assuming there is no load limit on the train. Given the transportation network and the orders, please help mzry1992 compute, for each customer who buys gold from him (i.e., his sell transactions), the quantity they purchase.

The first line contains three integers $n, m, q$, denoting the number of cities, the number of highways, and the number of cities with railway stations, respectively. The second line contains $n$ distinct integers, each between $1$ and $n$, representing a permutation of the cities: the order in which the orders arrive. The third line contains $n$ integers, where the $i$-th number is the upper limit $b_i$ of the order in city $i$. If $b_i > 0$, then from the perspective of mzry1992 it is a buy order (he buys gold) with upper limit $b_i$. If $b_i < 0$, then it is a sell order (he sells gold) with upper limit $-b_i$. Each of the next $m$ lines contains three integers $u, v, w$, meaning there is a bidirectional highway between cities $u$ and $v$ with load limit $w$. City indices are from $1$ to $n$. The last line contains $q$ integers, which are the indices of the cities that have railway stations.

In the order of the orders, for each sell transaction, output one line containing a single integer $x$, the amount of gold sold.

Sample explanation: - First sample: One valid plan is to initially buy $5$ units of gold in city $2$, take the third highway to city $1$, then take the train to city $3$, sell $3$ units of gold in city $3$, take the train back to city $1$, and sell $2$ units of gold in city $1$. - Second sample: One valid plan is to initially buy $4$ units of gold in city $1$, take the first highway, buy $3$ units of gold in city $2$, take the second highway, sell $6$ units of gold in city $3$, take the third highway, and sell $1$ unit of gold in city $4$. Constraints: - For $20\%$ of the testdata, $n \le 100$, $m \le 200$. - For $50\%$ of the testdata, $n \le 3000$, $m \le 6000$. - For $100\%$ of the testdata, $1 \le n \le 10^5$, $n - 1 \le m \le 2\times 10^5$, $0 \le q \le n$, $0 < |b_i| < 10^9$, $0 < w < 10^9$. It is guaranteed that any two cities are connected via highways. Translated by ChatGPT 5