P2966 [USACO09DEC] Cow Toll Paths G

Like everyone else, FJ is always thinking up ways to increase his revenue. To this end, he has set up a series of tolls that the cows will pay when they traverse the cowpaths throughout the farm. The farm is modeled as an undirected graph with $N$ pastures, conveniently numbered $1..N$, connected by $M$ bidirectional cowpaths. Path $j$ connects two different pastures $A_j$ and $B_j$ and has an edge toll $L_j$. There may be multiple cowpaths connecting the same pair of pastures, but no cowpath connects a pasture to itself. The graph is connected, so a cow can always move from any pasture to any other pasture by following some sequence of cowpaths. FJ has also assigned a toll $C_i$ to every pasture $i$. The cost of traveling from pasture $s$ to a different pasture $t$ along any path is the sum of the edge tolls on that path plus a single additional toll equal to the maximum of all the node tolls encountered along the way, including $s$ and $t$. You are given $K$ queries. Query $i$ specifies $(s_i, t_i)$ and asks for the minimum possible cost of a trip from $s_i$ to $t_i$ under the rule above.

- Line $1$: Three space-separated integers $N$, $M$, and $K$. - Lines $2..N+1$: Line $i+1$ contains a single integer $C_i$. - Lines $N+2..N+M+1$: Line $j+N+1$ contains three space-separated integers $A_j$, $B_j$, and $L_j$. - Lines $N+M+2..N+M+K+1$: Line $i+N+M+1$ contains two space-separated integers $s_i$ and $t_i$.

- Lines $1..K$: Line $i$ contains a single integer, the minimum cost of any route from $s_i$ to $t_i$.

Constraints: $1 \leq N \leq 250$, $1 \leq M \leq 10^4$, $1 \leq K \leq 10^4$, $1 \leq C_i \leq 100{,}000$, $1 \leq L_j \leq 100{,}000$. Notes: Multiple edges between a pair of pastures are allowed, but self-loops are not. The graph is connected. Translated by ChatGPT 5