P3096 [USACO13DEC] Vacation Planning G

Air Bovinia operates flights connecting the $N$ farms that the cows live on ($1 \le N \le 20{,}000$). As with any airline, $K$ of these farms have been designated as hubs ($1 \le K \le 200$, $K \le N$). Currently, Air Bovinia offers $M$ one-way flights ($1 \le M \le 20{,}000$), where flight $i$ travels from farm $u_i$ to farm $v_i$ and costs $d_i$ dollars ($1 \le d_i \le 10{,}000$). As with any other sensible airline, for each of these flights, at least one of $u_i$ and $v_i$ is a hub. There is at most one direct flight between two farms in any given direction, and no flight starts and ends at the same farm. Bessie is in charge of running the ticketing services for Air Bovinia. Unfortunately, while she was away chewing on delicious hay for a few hours, $Q$ one-way travel requests for the cows' holiday vacations were received ($1 \le Q \le 50{,}000$), where the $i$th request is from farm $a_i$ to farm $b_i$. As Bessie is overwhelmed with the task of processing these tickets, please help her compute whether each ticket request can be fulfilled, and its minimum cost if it can be done. To reduce the output size, you should only output the total number of ticket requests that are possible, and the minimum total cost for them. Note that this number might not fit into a $32$-bit integer. In other words, given a directed graph with $N$ nodes and $M$ edges, for each query find the shortest path whose route must pass through at least one node with an index in $1..K$.

- Line $1$: The integers $N$, $M$, $K$, and $Q$. - Lines $2..M+1$: Line $i+1$ contains $u_i$, $v_i$, and $d_i$. ($1 \le u_i, v_i \le N$, $u_i \ne v_i$.) - Lines $M+2..M+K+1$: Each of these lines contains the ID of a single hub (in the range $1..N$). - Lines $M+K+2..M+K+Q+1$: Two numbers per line, indicating a request for a ticket from farm $a_i$ to $b_i$. ($1 \le a_i, b_i \le N$, $a_i \ne b_i$.)

- Line $1$: The number of ticket requests that can be fulfilled. - Line $2$: The minimum total cost of fulfilling the possible ticket requests.

For the first flight, the only feasible route is $1 \to 2 \to 3$, costing $20$. There are no flights leaving farm $3$, so the poor cows are stranded there. Translated by ChatGPT 5