P4553 Around the World with 80 People

I’m sure many of you have seen Jackie Chan’s “Around the World in 80 Days,” and the intense, thrilling fight scenes must have left a deep impression. Now, there is a group of 80 people who also want to travel around the world. They plan to split up and visit every country. Since they are mainly located in the East, they will only move westward. Let the countries from east to west be numbered $1, \cdots, N$. If the $i$-th person’s itinerary is $P_1,P_2,\cdots ,P_k\ (0\le k\le N)$, then $P_1

The first line contains two positive integers $N, M$. The second line has $N$ positive integers, each not greater than $M$, representing $V_1,V_2,\cdots, V_N$. Then there are $N - 1$ lines. The $i$-th of these lines contains $N - i$ integers. The $j$-th number on this line is the airfare from the $i$-th country to the $(i + j)$-th country (if this value equals $-1$, then there is no direct flight between these two countries).

Output the minimal total cost on the first line.

- In $10\%$ of the testdata, $M=1$. - In $20\%$ of the testdata, $1\le M\le 2$. - In $40\%$ of the testdata, $1\le M\le 3$. - In $60\%$ of the testdata, $1\le M\le 4$. - In $100\%$ of the testdata, $1 \le N\le 100$, $1\le M\le 79$. It is guaranteed that for all input, the minimal cost is less than $10^6$. It is guaranteed that there exists at least one feasible plan. Jizhong League mock contest problem. By CQF. Translated by ChatGPT 5