P3627 [APIO2009] Robbery Plan

All roads in the city of Siruseri are one-way. Different roads are connected by intersections. By law, a Siruseri Bank ATM is installed at every intersection. Curiously, Siruseri’s bars are also located at intersections, although not every intersection has a bar. Banditji is planning the most spectacular ATM heist in the history of Siruseri. He will start from the city center, travel along one-way roads, rob all ATMs he passes, and finally celebrate his success at a bar. Using advanced hacking skills, he has learned the amount of cash that can be looted from each ATM. He wants you to help him calculate the maximum total cash he can rob, starting from the city center and ending at some bar. He may pass through the same intersection or road any number of times. However, once he has robbed an ATM, that ATM will no longer have any money. For example, suppose the city has $6$ intersections, and the road connections are as shown below:  The city center is at intersection $1$, marked by an entry arrow symbol →, and intersections with bars are shown with double circles. The amount of money available at each ATM is labeled above its intersection. In this example, the maximum total cash Banditji can rob is $47$, and one optimal robbery route is: $1-2-4-1-2-3-5$.

The first line contains two integers $N,M$. Here $N$ is the number of intersections, and $M$ is the number of roads. The next $M$ lines each contain two integers, both between $1$ and $N$. On the $(i+1)$-th line, the two integers denote the starting and ending intersection indices of the $i$-th road. The next $N$ lines each contain one integer, in order, representing the amount of money $a_i$ available at the ATM on each intersection. The next line contains two integers $S,P$. Here $S$ is the index of the city center, i.e., the starting intersection. $P$ is the number of bars. The next line contains $P$ integers, denoting the indices of the $P$ intersections that have bars.

Output a single integer, the maximum total cash Banditji can rob when starting from the city center and ending at some bar.

For $50\%$ of the testdata, it is guaranteed that $N, M \le 3000$. For $100\%$ of the testdata, it is guaranteed that $N, M \le 5\times 10^5$, $0 \le a_i \le 4000$. It is guaranteed that from the city center, along Siruseri’s one-way roads, at least one bar is reachable. Translated by ChatGPT 5