P8817 [CSP-S 2022] Holiday Plan

There are $n$ points on Little Bear’s map. Point $1$ is its home, and points $2, 3, \ldots, n$ are all scenic spots. Between some pairs of points, there are bidirectional direct bus lines. If there are direct lines between $x$ and $z_1$, between $z_1$ and $z_2$, $\ldots$, between $z_{k - 1}$ and $z_k$, and between $z_k$ and $y$, then we say that the trip from $x$ to $y$ can be completed with $k$ transfers. In particular, if there is a direct line between $x$ and $y$, then it can be completed with $0$ transfers. The holiday is coming soon. Little Bear plans to start from home and visit $4$ **different** scenic spots, then return home after completing $5$ segments of travel: home $\to$ spot A $\to$ spot B $\to$ spot C $\to$ spot D $\to$ home. Each segment may use at most $k$ transfers. There are no restrictions on the points passed during transfers: they can be home, scenic spots, and the same point may be passed multiple times. For example, in the segment from spot A $\to$ spot B, the points passed during transfers can include home, or spot C, and they may even include points that are passed during transfers in the segment spot D $\to$ home. Assume each scenic spot has a score. Please help Little Bear plan a route so that the sum of the scores of the four **different** scenic spots it visits is maximized.

The first line contains three integers $n, m, k$, representing the number of points on the map, the number of bidirectional directly connected pairs, and the maximum number of transfers allowed for each segment. The second line contains $n - 1$ positive integers, representing the scores of scenic spots numbered $2, 3, \ldots, n$. The next $m$ lines each contain two positive integers $x, y$, indicating that points $x$ and $y$ are directly connected by a road. It is guaranteed that $1 \le x, y \le n$, and there are no multiple edges or self-loops.

Output one positive integer, the maximum possible sum of the scores of the $4$ different scenic spots that Little Bear visits.

**[Sample Explanation #1]** When the planned route is $1 \to 2 \to 3 \to 5 \to 7 \to 1$, the sum of the scores of the $4$ scenic spots is $9 + 7 + 8 + 3 = 27$. It can be proven that this is the maximum. The sum of scenic spot scores for the route $1 \to 3 \to 5 \to 7 \to 8 \to 1$ is $24$, and for the route $1 \to 3 \to 2 \to 8 \to 7 \to 1$ is $25$. They both meet the requirements, but their sums are not the maximum. The sum of scenic spot scores for the route $1 \to 2 \to 3 \to 5 \to 8 \to 1$ is $30$, but in it, $5 \to 8$ requires at least $2$ transfers, so it does not satisfy the requirement of at most $k = 1$ transfer. The sum of scenic spot scores for the route $1 \to 2 \to 3 \to 2 \to 3 \to 1$ is $32$, but the trip does not visit $4$ different scenic spots, so it also does not meet the requirements. **[Sample #3]** See `holiday/holiday3.in` and `holiday/holiday3.ans` in the attachment. **[Constraints]** For all testdata, it is guaranteed that $5 \le n \le 2500$, $1 \le m \le 10000$, $0 \le k \le 100$, and for all scenic spots, $1 \le s_i \le {10}^{18}$. It is guaranteed that there exists at least one route that meets the requirements. | Test Point ID | $n \le$ | $m \le$ | $k \le$ | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $10$ | $20$ | $0$ | | $4 \sim 5$ | $10$ | $20$ | $5$ | | $6 \sim 8$ | $20$ | $50$ | $100$ | | $9 \sim 11$ | $300$ | $1000$ | $0$ | | $12 \sim 14$ | $300$ | $1000$ | $100$ | | $15 \sim 17$ | $2500$ | $10000$ | $0$ | | $18 \sim 20$ | $2500$ | $10000$ | $100$ | Translated by ChatGPT 5