P4046 [JSOI2010] Courier Service

After the “Feiben” (pinyin) courier company was founded, it signed mail pickup-and-delivery service contracts with many small and medium-sized companies in the city. Since some companies are in the same building, the pickup locations (pickup points) that “Feiben” needs to visit are at most $m$ points ($1, 2, \dots, m$). Therefore, “Feiben” purchased three trucks and hired three drivers, who set out every morning from pickup locations $1, 2, 3$ respectively. The service contract with clients clearly states that “Feiben” must send someone to the client’s company (location) to pick up the mail on the day after the client submits the mailing request. To serve clients more efficiently and save pickup time, the company set up a pickup service registration website. If a client needs to send mail, they must register online one day in advance. To save fuel, “Feiben” plans the next day’s pickup routes for the three drivers at night. The order in which each driver visits their assigned locations must respect the online registration order, and all pickups must be completed using the least fuel. Thus, a driver may need to visit the same location multiple times at different times, and different drivers may also go to the same location at different times. As shown in Example 2 below (the pickup locations in order are: `4 2 4 1 5 4 3 2 1`), although driver $1$ starts at pickup location $1$, he cannot first pick up the mail for the fourth registered company (location $1$) and then go to the first, second, or third registered pickup locations (locations $4, 2, 4$). However, if the first three registered pickups are handled by driver $2$ or $3$, then driver $1$ can pick up the fourth registered mail at location $1$ and then proceed to later registered locations. In some cases, not every truck needs to pick up mail; the optimal plan may use only one or two trucks. Please write a program to compute the minimum total fuel consumption to visit all pickup locations in the registered order. Brief statement: Given an $m \times m$ matrix $D$. We define the cost of a sequence $a(a_0, a_1, a_2, \dots, a_n)$ as $\sum\limits_{i=1}^{n} D_{a_{i-1}, a_i}$. Now you are given a sequence $s$ with length $\leq 1000$. Split it into three subsequences $a, b, c$, with $a_0 = 1, b_0 = 2, c_0 = 3$. Among all such partitions, minimize the sum of their costs. In particular, the matrix $D$ satisfies the triangle inequality; see the detailed explanation in the Input Format. (By El_destructor.)

The first line of the input file contains an integer $m$, the number of pickup locations, identified by integers from $1$ to $m$. The next $m$ lines (lines $2$ to $m+1$) each contain $m$ integers, representing a matrix $D$. On the $i$-th line, the $j$-th integer $D(i, j)$ is the fuel required to drive from pickup point $i$ to pickup point $j$. The last line is a sequence of location IDs in the order of the requests registered online on the previous day; there are at most $1000$ pickup requests. Any two adjacent integers in the input are separated by one space. Note: The fuel matrix $D$ satisfies the triangle inequality, that is, $\forall 1 \leq i, j, k \leq m, D(i, j) \leq D(i, k) + D(k, j)$. Therefore, when a truck goes to the next assigned pickup location, it always goes directly without detouring through other locations.

Output a single integer, the minimum total fuel required for all pickups.

Sample explanation: The drivers assigned to each request, in order, are `1 1 1 1 3 3 2 2 2 1`. Therefore, driver $1$ only needs to move from starting point $1$ to location $3$, driver $2$ can stay at location $2$, and driver $3$ moves from starting point $3$ to location $4$. Constraints: $3 \leq m \leq 200, 1 \leq s_i \leq m$. Translated by ChatGPT 5