P3094 [USACO13DEC] Vacation Planning S

There are $N$ farms numbered $1..N$ with $1 \le N \le 200$. The airline plans to set up flight routes between the farms. Among these farms, those numbered $1..K$ are designated as hub farms, where $1 \le K \le 100$ and $K \le N$. There are currently $M$ directed flights ($1 \le M \le 10{,}000$). Each flight goes from farm $u_i$ to farm $v_i$ and costs $d_i$ dollars, with $1 \le d_i \le 1{,}000{,}000$. The airline has received $Q$ ($1 \le Q \le 10{,}000$) directed trip requests. The $i$th request is to travel from farm $a_i$ to farm $b_i$. A valid trip must pass through at least one hub farm (it may be the starting or ending farm). The route may visit the same farm multiple times. Compute the number of trip requests for which a valid route exists, and the total cost to complete all valid requests, where each valid request is taken with its minimum possible route cost.

* Line 1: Four integers: $N$, $M$, $K$, and $Q$. * Lines $2..1+M$: Line $i+1$ contains $u_i$, $v_i$, and $d_i$ for flight $i$. * Lines $2+M..1+M+Q$: Line $1+M+i$ describes the $i$th trip in terms of $a_i$ and $b_i$.

* Line 1: The number of trips (out of $Q$) for which a valid route is possible. * Line 2: The sum, over all trips for which a valid route is possible, of the minimum possible route cost.

There are three farms (numbered $1..3$); farm $1$ is a hub. There is a 10-dollar flight from farm $3$ to farm $1$, and so on. We wish to look for trips from $3 \to 2$, from $2 \to 3$, and from $1 \to 2$. The trip from $3 \to 2$ has only one possible route, with cost $10+7$. The trip from $2 \to 3$ has no valid route, since there is no flight leaving farm $2$. The trip from $1 \to 2$ has only one valid route again, with cost $7$. Translated by ChatGPT 5