P1690 Greedy Copy

Copy heard from Lu Niu that many treasures are buried in a divine land called yz, so Copy came to this land, which is divided into $n$ regions. Lu Niu told Copy that there are in total $P$ treasures, each placed in region $P_i$ ($1 \le P_i \le n$). Copy also learned the distance between every pair of regions. Now Copy starts from region $1$, wants to collect all treasures, and leave from region $n$. Copy is lazy, so he asks you to find a suitable route that minimizes the total distance he needs to travel.

- The first line contains a positive integer $n$ ($1 \le n \le 100$). - The next $n$ lines each contain $n$ integers; the number in row $i$, column $j$ denotes the distance from region $i$ to region $j$. The numbers are separated by spaces, and each distance is at most $1000$. Note that the distance $i \to j$ is not necessarily equal to $j \to i$. - The next line contains an integer $P$ ($0 \le P \le 10$). - The next line contains $P$ integers separated by spaces, denoting the indices of the regions that contain treasures.

Output a single integer: the minimum total distance for Copy to collect all treasures and then reach region $n$. The testdata guarantees that the answer is at most $2^{31} - 1$.

- For $30\%$ of the testdata, $1 \le n \le 15$; the rest are as stated. - For $100\%$ of the testdata, all constraints are as stated. Translated by ChatGPT 5