406985: GYM102646 C Song Optimization

One of the hardest parts about learning how to play the guitar is transitioning between different chords, as they can require complicated finger positions. In total, there are $$$k$$$ chords. It takes Timmy $$$s_{i, j}$$$ seconds to switch from being able to play chord $$$i$$$ to chord $$$j$$$.

Timmy has to play a song that consists of $$$n$$$ notes, and he wants to do it quickly so he can practice as much as possible. The total time it takes him to play a song is the time it takes for him to transition from each chord to the next one, in order, until the end of the song is reached. You can assume the song starts when he plays the first chord, that is, he immediately starts ready to play the first chord.

However, when transitioning between a chord $$$i$$$ and a chord $$$j$$$, he may not directly switch from $$$i$$$ to $$$j$$$. Instead, he may switch from $$$i$$$ to some sequence of intermediate chords to get to $$$j$$$ if it's faster for him. For example, if the song requires him to switch from chord $$$1$$$ to chord $$$7$$$, one possible way for him to do this is to switch from chord $$$1$$$ to $$$6$$$, $$$6$$$ to $$$3$$$, and finally $$$3$$$ to $$$7$$$, if it's faster than switching directly from $$$1$$$ to $$$7$$$.

To minimize the time it takes him to play the song, he can change at most one chord in the song to a different one. What is the minimum time required to play the song he can achieve?

The first line contains two space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 100)$$$. The next $$$k$$$ lines contains $$$k$$$ space-separated integers each. On line $$$i$$$ of these $$$k$$$ lines, the $$$j$$$-th integer denotes $$$s_{i, j}$$$ $$$(1 \leq s_{i, j} \leq 10^9)$$$: the time it takes Timmy to switch from chord $$$i$$$ to chord $$$j$$$. It is guaranteed that for all $$$i$$$, $$$s_{i, i} = 0$$$. The last line contains $$$n$$$ space-separated integers each, with the $$$i$$$-th integer denoting the $$$i$$$-th chord in the song.

Print a single integer - the minimum time required to play the song Timmy can achieve.

5 3
0 1 5
5 0 3
3 1 0
1 2 3 2 1

5

7 4
0 1 100 100
100 0 1 1
1 1 0 100
100 100 100 0
1 3 3 1 4 3 1

6

One optimal solution for sample 1 is the order $$$1, 2, 3, 2, 2$$$. Timmy will start at $$$1$$$, transition from $$$1$$$ to $$$2$$$ ($$$1$$$ second), $$$2$$$ to $$$3$$$ ($$$3$$$ seconds), $$$3$$$ to $$$2$$$ ($$$1$$$ second), and $$$2$$$ to $$$2$$$ ($$$0$$$ seconds), for a total of $$$5$$$ seconds.

One optimal solution for sample 2 is the order $$$1, 3, 3, 1, 1, 3, 1$$$. Timmy will start at $$$1$$$, transition from $$$1$$$ to $$$2$$$ to $$$3$$$, $$$3$$$ to $$$3$$$, $$$3$$$ to $$$1$$$, $$$1$$$ to $$$1$$$, $$$1$$$ to $$$2$$$ to $$$3$$$, and $$$3$$$ to $$$1$$$, for a total of $$$6$$$ seconds. Note that it's faster for Timmy to transition from $$$1$$$ to $$$2$$$ to $$$3$$$ rather than directly transitioning from $$$1$$$ to $$$3$$$.